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

Комбинаторика

Основная задача комбинаторики – пересчет и перечисление элементов в конечных множествах. Первая задача состоит в вычислении числа элементов, обладающих заданным свойством или набором свойств. Вторая – состоит в выделении всех интересующих нас элементов. Если на исходном множестве определена некоторая целевая функция, экстремум которой необходимо найти, то решение задачи оптимизации в сильном смысле – это отыскание всех элементов, на которых достигается экстремум, а в слабом смысле – это нахождениепроизвольного элемента, доставляющего экстремум целевой функции.

При решении задач оптимизации обычно предполагается наличие методов перечисления элементов исходного множества, а для оценки эффективности методов перечисления или оптимизации часто целесообразно решать задачу пересчета элементов в исходном множестве или в некоторых его подмножествах.

Комбинаторные схемы

Пусть задано конечное множество Х, такое, что . Тогда объект из Х может быть выбран n способами. Пусть множества Х_i, где таковы, что и , если i¹j. Тогда выполняется равенство

Этот факт в комбинаторике называется правилом суммы, которое утверждает, что так как объект можно выбрать n_i способами из Х ( ÎХ_iÌХ), то выбор из Х либо , либо , либо можно осуществить n₁+n₂+…+n_k способами.

В другом случае, если мы будем осуществлять выбор упорядоченного набора (кортежа) < , ,…, >, где ÎX_i, то очевидно, что такой набор можно осуществить способами. Это следует из равенства

.

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

Задача 2.1. Найти число возможных десятичных четырехзначных чисел (не начинающихся, естественно, с нуля).

Решение. Для первого символа (слева) , для остальных символов , . Следовательно, число всех возможных комбинаций <a₁, a₂, a₃, a₄>, где a₁¹0, равно .

Схемы без повторений

Пусть мы имеем конечное множество Х={ , ,…, }, тогда набор элементов ,…, называется выборкой объема r из n элементов или, иначе, (n,r)-выборкой. Выборка называется упорядоченной, если порядок следования элементов в ней фиксирован, и две выборки, различающиеся лишь порядком следования элементов, считаются различными.

Число возможных различных упорядоченных (n,r)-выборок с такими элементами, что ¹ , если и j¹k равно числу различных r-векторов < ,…, >, которые могут быть построены на Х={ ,…, }. Это число называется числом размещений из n элементов по r и обозначается . Докажем, что

, (2.1)

где и называется k-факториал.

Очевидно, что для выбора у нас есть n возможностей. После выбора элемента и удаления его из Х, для выбора остается (n-1) возможность и т.д. Тогда при выборе элемента имеется [n-(r-1)] возможностей и в итоге имеем

.

Если рассмотреть множество всех различных n-векторов <x_i1, x_i2,…,x_in>, которые можно построить на Х, то каждая такая выборка называется перестановкой, поскольку различаются они только расположением элементов. Перестановки обозначаются Р_n. Докажем, что

. (2.2)

Для этого выберем первый элемент ÎХ и рассмотрим все перестановки, в которых имеет номер 1. Число таких перестановок с очевидностью равно Р_n-1. Обозначим через М множество всех перестановок множества Х, а через М_i – множество всех перестановок, в которых имеет номер i. Тогда

М=М₁ÈМ₂È…ÈМ_n,

где , если i¹j, поскольку элементы множеств М_i и М_j различаются положением элемента .

Используя предыдущий вывод, что |М_i|=Р_n-1, , можно записать

.

Используя (2.1) для размещений , соответствующих упорядоченным выборкам (n,n), можно записать:

С другой стороны, эти выборки соответствуют n-перестановкам, и из (2.2) следует, что

откуда мы должны положить 0!=1.

Рассмотрим теперь неупорядоченные выборки { ,…, } r-элементов из Х, которые считаются различными, если они отличаются хоть одним элементом. Таким образом, каждая такая (n,r)-выборка есть подмножество мощности r множества Х. Задача состоит в подсчете числа разных r-элементных подмножеств из n-элементного множества Х. Каждое такое подмножество называется сочетанием из n-элементов по r, а их общее число обозначается . Покажем, что

. (2.3)

Для этого можем заметить, что каждой выборке (сочетанию) { ,…, } соответствует r! упорядоченных выборок (размещений) < ,…, > за счет перестановок r элементов, то есть

,

откуда следует после применения (2.1), что

.

Задача 2.2. Сколькими способами можно упорядочить множество {1,2,…,2n-1, 2n} так, чтобы каждое четное число имело четный номер?

Решение. Задача состоит в расположении нечетных чисел (их всего n) по нечетным, а четных (их тоже n) - по четным местам.

Очевидно, что первая подзадача имеет решение n!. Но точно так для каждой комбинации нечетных чисел имеется n! перестановок четных чисел по четным местам. В итоге общее число комбинаций равно n! *n!= (n!)².

Задача 2.3. Сколько существует способов упорядочить множество {1,2,…,n} так, чтобы числа 1,2,3 стояли рядом и в порядке возрастания?

Решение. Число 1 (а 2 и 3 должны стоять рядом справа) можно записать на 1-е, 2-е,…,(n-2)-е место, то есть всего (n-2) возможности. В каждом случае оставшиеся (n-3) чисел могут быть расставлены (n-3)! способами. Таким образом, число интересующих нас комбинаций равно (n-2)(n-3)!.

Задача 2.4. При повороте листа бумаги с цифрами на 180°цифры 0,1,8 не изменяются, 6 и 9 переходят друг в друга, а остальные теряют смысл. Сколько существует семизначных чисел, не содержащих одинаковых цифр и не изменяющихся при повороте листа?

Решение. Очевидно, что 4-е место (центральное) в числе могут занимать 0,1 или 8. Это составляет 3 возможности. Для каждой из этих возможностей для тройки чисел справа (или слева) от центральной цифры нужно из четырех оставшихся цифр составить комбинацию из трех цифр. Всего таких комбинаций , а следовательно, общее число возможных искомых семизначных чисел равно N=3*24=72.

Задача 2.5. На плоскости заданы n точек, все попарно соединенные линиями, называемые ребрами. Сколько всего ребер?

Решение. Пусть каждой точке соответствует элемент множества X={ ,…, }. Тогда каждое ребро определяет подмножество X, состоящее из двух элементов, и задача состоит в отыскании числа всех 2-х элементных подмножеств в X, которое равно числу сочетаний:

Рис.2.1. Схема одного из кратчайших путей на сетке

Задача 2.6. На прямоугольной сетке m´n (рис. 2.1) найти число различных кратчайших путей, соединяющих точки (0,0) и (m,n).

Решение. Любой кратчайший путь из (0,0) в (m,n) состоит из m+n отрезков, среди которых m горизонтальных и n вертикальных. Разные пути различаются лишь порядком чередования горизонтальных и вертикальных отрезков. Поэтому их число равно числу способов выбора мест n вертикальных отрезков на общем числе шагов m+n, т.е. числу сочетаний Очевидно, этот же результат будет получен, если размещать m горизонтальных отрезков на n+m шагах, а, следовательно,

. (2.4)

Применяя, использованный в задаче 2.5 так называемый метод траекторий, можно доказать тождество

. (2.5)

Действительно, из рисунка 2.1 следует, что общее число кратчайших путей из в равно сумме путей, ведущих из в точку А₁ с координатами в точку A₂ с координатами , т.е.:

.

Переобозначив m+n=r, получим формулу (2.5):

.

Точно так же можно доказать, что

. (2.6)

Для этого на рисунке 2.1 положим, что m=n и обратим внимание, что в соответствии с (2.4) общее число кратчайших путей из (0,0) в (n,n) равно С другой стороны, каждый из этих путей проходит через одну и только одну из точек A_k (k,n-k), лежащих на диагонали, соединяющей точки (0,n) и (n,0). Тогда число различных путей из (0,0) в (n,n), проходящих через A_k (k,n-k), равно произведению числа путей, ведущих в A_k и из A_k в (n,n), т.е.

. (2.7)

Суммируя по всем точкам k=0,1,…,n, получим выражение, стоящее справа в (2.6).

Числа называются также биноминальными коэффициентами, что связано с формулой бинома Ньютона:

(2.8)

Докажем эту формулу, используя представление:

.

Перемножая последовательно (a+b) n раз, получим сумму 2ⁿслагаемых вида где равно a или b. Разобьем слагаемые на n+1 группу B₀,B₁,B₂,…,B_n, отнеся к B_k все те произведения, в которых b встречается множителем k раз, а a - (n-k) раз. Число произведений в B_k равно числу способов выбора k мест из возможных n мест, т.е. равно , а каждое слагаемое в равно a^n-kb^{k .}. Поэтому

.

Схемы с повторениями

Поставим такой вопрос: сколькими способами можно разложить множество A={a₁,a₂,…,a_n}на m подмножеств

,

таких, что

?

Описанные разбиения можно получить так: возьмем произвольно k₁-элементное подмножество B₁ÌA (выбор можно осуществить способами), из оставшихся n-k₁ элементов выберем k₂ -элементное подмножество B₂ÌA\B₁ (выбор можно осуществить способами) и т.д. Тогда по правилу умножения общее число способов равно:

Полученные числа, равные числу перестановок с повторениями

, (2.9)

называются полиномиальными коэффициентами, так как они связаны с полиномиальной формулой:

(2.10)

Перемножив последовательно a₁+…+a_m n раз, получим слагаемых вида , где каждый множитель равен , или , …или . Пусть B(r₁,r₂,…,r_k) - совокупность всех тех слагаемых, где a₁ встречается r₁ раз, a₂ - r₂ раз,…, a_k - r_k раз, причем r₁+r₂+…+r_k=n. Число таких слагаемых равно числу способов представления множества из n элементов k подмножествами, т.е. используя (2.9)

B(r₁,r₂,…,r_k)=C_n(r₁,r₂,…,r_k),

а, следовательно, справедливо соотношение (2.10). При k=2, очевидно, получим форму бинома Ньютона.

Еще одна комбинаторная интерпретация коэффициентов (2.9) может быть дана, если для множества n букв, из которых k₁ – букв a₁, k₂ – букв a₂,…,k_m – букв a_m , k₁+k₂+…+k_m=n. Определим число различных слов длины n. Перенумеровав места, на которых стоят буквы номерами {1,2,…,n}, мы каждое слово определим множествами B₁(номера мест, где стоит буква a₁),B₂(номера мест, где стоит a₂),…,B_m(номера мест, где стоит буква a_m). Таким образом, число различных слов равно числу способов, которыми можно представить множество A={1,2,…,n} в виде т.е. .

Если рассмотреть множество элементов A={a₁,…,a_m}, то можно поставить вопрос о вычислении числа групп (сочетаний) B_k={b₁,…,b_n}, где b_i, может быть равно одному из a_j, .

Например, если A={ } и n=2, то имеем сочетания с повторениями:

(2.11)

Число различных сочетаний из m элементов по n с повторениями равно

. (2.12)

Для доказательства этой формулы укажем, сколько элементов из A входит в сочетание. Поставим в соответствие каждому сочетанию последовательность нулей и единиц, составленную по правилу: напишем подряд столько единиц, сколько элементов входит в сочетание, далее поставим нуль и после этого напишем столько единиц, сколько элементов в сочетании, и т.д. Например, сочетаниям (2.11) соответствуют последовательности:

1100, 1010, 1001, 0110, 0101, 0011.

Таким образом, каждому сочетанию из m по n однозначно соответствует последовательность n единиц и m-1 нулей. Поэтому число сочетаний из m по n с повторениями равно

.

Задача 2.7. Найти число возможных размещений n одинаковых элементов в m урнах.

Решение. Рассмотрим одно из возможных размещений элементов в урнах следующим способом (рис. 2.2): поместим в урну столько единиц, сколько там элементов, расположив между урнами по нулю. Тогда «слово», составленное из единиц в урнах и нулей между ними, будет содержать m+n-1 символ, из которых n единиц и (m-1) нулей. Следовательно, общее число различных размещений равно

.

Рис.2.2. Распределение элементов по урнам так, чтобы

Задача 2.8. Найти число распределений m+n+s различных элементов на 3 группы по m,n и s элементам каждая.

Решение. Очевидно, что требуется разбить исходное множество A={a₁,…,a_m+n+s} на три подмножества ½A₁½=m,½A₂½=n,½A₃½=s. Используя формулу (2.9), можно записать:

Задача 2.9. Сколько целых неотрицательных корней имеет уравнение: x₁+x₂+…+x_m=n?

Решение. Очевидно, что каждое , может принимать значения 0,1,…,n и их сумма должна быть равна n. Тогда задача состоит в отыскании числа сочетаний из m элементов (по числу переменных) по n (общее число элементов), т.е. по формуле (2,12):

.

Задача 2.10. Сколько целых положительных решений имеет неравенство (m£n)

Решение. Если произвести замену с использованием тривиального решения x_i=1, i=1,m, x_i=1+y_i, то исходное неравенство приобретает вид y₁+y₂+…+y_m£n-m. Тогда для каждого k=1,2,…,n-m число решений уравнения y₁+y₂+…+y_m=k равно в соответствии с решениями задачи 9 равно , а общее число решений исходного неравенства равно:

Рассмотрим теперь выборки из n по r, в которых элементы упорядочены и допускаются повторения элементов. Это так называемые (n,r)-размещения с повторениями. Так, для множества X={1,2,3,} такими (3,2)-размещениями будут:

<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>.

Покажем, что число таких размещений равно:

. (2.13)

Действительно, при выборе первого элемента в выборке у нас имеется n возможностей, при выборе второго тоже – n и т.д., всего r раз. Таким образом, по правилу умножения получим:

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

Если X₁,X₂,…,X_n некоторые подмножества множества X, причем в общем случае , то справедлива формула (1.47), которая в комбинаторике называется формулой включений и исключений:

|X₁È…ÈX_n|=(|X₁|+…+|X_n|)-(|X₁ÇX₂|+|X₁ÇX₃|+…+|X_n-1ÇX_n|)+

+(|X₁ÇX₂ÇX₃|+…+|X_n-2ÇX_n-1ÇX_n|)-…+(-1)ⁿ⁺¹|X₁Ç…ÇX_n|. (2.14)

Следствием этой формулы является равенство:

|X\(X₁È…ÈX_n)|=|X|-(|X₁|+…+|X_n|)+(|X₁ÇX₂|+…+|X_n-1ÇX_n|)-+

+(-1)ⁿ|X₁Ç…ÇX_n|. (2.15)

Действительно,

[X\(X₁È…ÈX_n)]È(X₁È…ÈX_n)=X,

[X\(X₁È…ÈX_n)]Ç(X₁È…ÈX_n)=Æ,

откуда

|X\(X₁È…ÈX_n)|+|X₁È…ÈX_n|=|X|,

а, следовательно,

|X\(X₁È…ÈX_n)|=|X|-|X₁È…ÈX_n|. (2.16)

Для получения (2.15) остается только подставить (2.14) в (2.16).

Более распространенная форма записи формулы включений и исключений может быть получена при рассмотрении конечного множества X, такого что |X|=n и заданных свойств a₁,…,a_k, которыми элементы X могут обладать или не обладать.

Обозначим: – множество элементов в Х, обладающих свойством

- количество элементов в , обладающих одновременно свойствами ; - количество элементов в , не обладающих ни одним из свойств . Тогда по формуле (2.15) получаем

, (2.17)

где

Задача 2.11. Пусть Х={0,1,...,10}; : « – чётные»; : « », : « ». Найти количество элементов в , не обладающих свойствами .

Решение. Используя формулу (2.15) и (2.17) получаем , в следствии того, что , , , . Очевидно, что этим единственным элементом в является число 1.

Задача 2.12. (Задача о беспорядках). Имеется n различных предметов и столько же различных ячеек . Сколькими способами можно разложить предметы по ячейкам так, чтобы никакой предмет не попал в ячейку ?

Решение. Роль исходного множества выполнит множество всевозможных распределений по ячейкам. Число таких множеств равно числу перестановок . Введём свойства ai: « находится в ячейке », . Число расположений, при которых находится в ячейке , равно . Тогда

Используя формулу включений и исключений, получаем число распределений, при которых ни одно из свойств не выполняется, и оно равно: