Формула включений и исключений.

В машиностроении рассматриваются конечные множества. Чтобы подсчитать число элементов конечного множества, образованного в результате объединения или пересечения некоторых конечных множеств, используется комбинаторный анализ. Мы рассмотрим теоремы сложения и умножения, а так же формулу включений и исключений.

Теорема 2.2. (Теорема сложения)

Пусть – конечные попарно непересекающиеся множества, т.е. . Тогда

(2.3.1.)

Доказательство. Докажем теорему методом математической индукции.

Базис индукции. Пусть n=2. Пусть множества X₁=A и X₂=B, мощности которых соответственно равны k₁ и k₂, т.е. |A|=k₁, |B|=k₂. Так как AÇB=Æ, то

.

Индуктивный переход. Пусть теорема верна для n. Покажем, что для n+1 будет тоже справедливо. Тогда

■

Теорема 2.3. (Теорема умножения)

Пусть заданы конечные множества . Тогда

(2.3.2.)

т.е. число элементов декартова произведения множеств равно произведению количеств элементов сомножителей.

Доказательство. Докажем теорему методом математической индукции.

Базис индукции. Пусть n=2. Пусть множества X₁=A и X₂=B, мощности которых соответственно равны k₁ и k₂, т.е. |A|=k₁, |B|=k₂. Первый компонент упорядоченной пары можно выбрать k₁ способами, второй – k₂ способами. Таким образом, всего имеется k₁×k₂ различных упорядоченных пар. Значит,

.

Индуктивный переход. Предположим справедливость утверждения теоремы для n. Покажем, что для n+1 оно будет тоже справедливо. В самом деле, добавляя еще одно множество в декартово произведение, видим, что

■

Пример 2.7. Сколько существует целых чисел между 0 и 1000, содержащих ровно одну цифру 6?

Решение. Пусть S – множество целых чисел между 0 и 1000, содержащих ровно одну цифру 6. Рассмотрим три подмножества S₁, S₂ и S₃ множества S.

S₁ – множество, которое содержит число, состоящее из одной цифры, и эта цифра 6;

S₂ – множество, содержащее двузначные числа ровно с одной цифрой, равной 6;

S₃ – множество, содержащее трехзначные числа ровно с одной цифрой, равной 6.

Множество S₁ содержит только один элемент – число 6. Значит, | S₁|=1.

В множестве S₂ каждый элемент, содержащей 6, имеет ее либо первой, либо второй цифрой. Если 6 – вторая цифра, то существует 8 различных чисел, которые будут стаять на первом месте, поскольку первое число не может быть 0 или 6. Если 6 – первая цифра, то таких чисел 9, поскольку вторая цифра не может быть 6. Таким образом, S₂ содержит 8+9=17 элементов, т.е. | S₂|=17.

Элемент из S₃ содержит 6 как первою, вторую или третью цифру. Если 6 – первая цифра, то существует 9 вариантов выбора второй цифры и 9 вариантов выбора третьей цифры. Согласно комбинаторному принципу умножения, S₃ содержит 9 ´9=81 чисел с первой цифрой. Если 6 – вторая цифра, то имеются 9 вариантов выбора третьей цифры и 8 вариантов выбора первой цифры, поскольку первая цифра не может быть нулем. Следовательно, S₃ содержит 9´8=72 числа, у которых 6 – вторая цифра. Аналогично, S₃ содержит 72 числа, у которых 6 – третья цифра. Следовательно, всего S₃ содержит 81+72+72=225 элементов, т.е. |S₃|=225.

Поскольку и множества S₁, S₂ и S₃ попарно непересекающиеся, то

.

,

Поставим задачу подсчитать число элементов в объединении

X=X₁ÈX₂È…ÈX_m

конечных множеств , которые могут иметь непустые пересечения между собой, т.е. объединение может быть не разбиением. В общем случае имеет место следующая теорема, которую нетрудно доказать методом математической индукции. Но мы примем теорему без доказательства.