ТЕОРИЯ КОНЕЧНЫХ МНОЖЕСТВ (КОМБИНАТОРИКА) §1. Принципы сложения и умножения Комбинаторика занимается подсчетом количеств разных комбинаций, которые можно получить различными способами из тех или иных конечных множеств.

Если конечное множество A состоит из m элементов, то мы будем писать: |A| = m или n(A) = m. Теорема 1 (принцип сложения). Пусть A B =. Тогда n(A B) = n(A) + n(B). Следствие 2. Пусть A 1, A 2 ….A l – система попарно непересекающихся конечных множеств. Тогда n(A 1 A 2 … A l ) = n(A 1 )+n(A 2 )+…+n(A l ).

Доказательство: При l=2 ссылаемся на теорему 1: n(A 1 A 2 ) = n(A 1 ) + n(A 2 ). Допустим, что утверждение верно при l = k, n(A 1 A 2 … A k ) = n(A 1 ) + n(A 2 ) +…+ n(A k ). Докажем утверждение при l = k+1. В этом случае n(A 1 A 2 … A k A k+1 ) = n((A 1 A 2 … A k ) A k+1 ) = n(A 1 A 2 … A k ) + n(A k+1 ). Здесь мы воспользовались базисом индукции и, применяя индуктивное предположение, получим: n(A 1 A 2 … A k ) + n(A k+1 ) = n(A 1 ) +…+ n(A k ) + n(A k+1 ). Следствие доказано.

Иногда принцип сложения можно встретить в таком виде: если объект x можно получить m способами, а объект y можно получить l способами, причем множества этих способов не пересекаются, то объект x или объект y можно получить m + l способами. Таким образом, необходимо помнить, что в комбинаторике союз или ассоциирован с операцией сложения.

Теорема 3 (принцип умножения). Если множество A состоит из m элементов, а множество B состоит из l элементов, то n(A B) =ml. Доказательство: При l=1 множествоB состоит из 1 элемента: B={b 1 }. Поэтому мн-во A B={(a i, b 1 )|i =1, 2,…,m}состоит из m элементов, n(A B)=m · 1=m · l. Базис индукции проверен. При l = k, если n(A) = m, n(B) = k, то n(A B) = m · k. При l = k + 1. Пусть B = {b 1, b 2,…, b k, b k+1 } или B=B {b k+1 },

Где множествоB ' ={b 1, b 2,…, b k }состоит из k элементов. По индуктивному предположению n(A B ' ) = n(A) · n(B ' ) = m · k. С другой стороны B=B {b k+1 }, поэтому (A B) = A B ' A … {b k+1 }, причем A B ' A {b k+1 } =, так как B ' {b k+1 } =. По теореме 1 n(A B) = n(A B ' A {b k+1 }) = n(A B ' ) + n(A {b k+1 })=m · k + m · 1 = m(k + 1) = m · l.

В комбинаторном изложении принцип умножения часто формулируют так: если объект x можно сконструировать m способами, объект y можно сконструировать l способами, то объект (x, y) или (x и y) можно сконструировать m · l способами. То есть союз и в комбинаторики ассоциирован с операцией умножения.

Теорема 4. Если множества A 1, A 2, …, A k конечны, то n(A 1 A 2,…, A k )=n(A 1 ) · n(A 2 )·,…, ·n(A k ).

Задача. Пусть A и B конечные мн-ва, B A. Сколько элементов содержит множества A \ B. Решение. Докажем, что в случае, когда B A, n(A \ B) = n(A) – n(B). В самом деле, запишем очевидное теоретико- множественное равенство (A \ B) B = A, причем (A \ B) B =. Применим к множествам A \ B и B принцип сложения. n((A \ B) B)=n(A \ B) + n(B) или n(A)=n(A \ B)+n(B) Отсюда получаем требуемое равенство n(A \ B) = n(A) – n(B).

Задача. Из цифр A={0,1,2,3,5,6,7} составить все четырех­значные числа, не содержащие повторяющихся цифр и делящиеся на 3. Решение. Воспользуемся признаком делимости на три: число делится на три в том и только в том случае, когда сумма цифр этого числа делится на три. Поэтому надо перебрать всевозможные четверки цифр, сумма которых делится на три. Перечислим такие четверки:

A 1 = {0, 1, 2, 3}, A 2 = {0, 1, 2, 6}, A 3 = {0, 1, 3, 5}, A 4 = {0, 1, 5, 6}, A 5 = {0, 2, 3, 7}, A 6 = {0, 3, 5, 7}, A 7 = {0, 5, 6, 7}, A 8 = {1, 2, 3, 6}, A 9 = {1, 3, 5, 6}, A 10 = {1, 2, 5, 7}, A 11 = {2, 2, 6, 7}, A 12 = {3, 5, 6, 7}. Обозначим через B множество всех искомых чисел, а через B i (i = 1, 2,…, 12) множества чисел, полученные из цифр множества A i соответственно. Так как при i j B i B j =, то по принципу сложения n(B) =. По принципу произведения n(B 1 )=3·3·2·1=18.

Аналогично n(B 2 )=n(B 3 )=n(B 4 )=n(B 5 )=n(B 6 )=n(B 7 )=18 По принципу произведения n(B 8 )=4·3·2·1=24. Аналогично, n(B 9 )=n(B 10 )=n(B 11 )=n(B 12 )=24. Наконец, n(B)=18·7+24·5=246

§2. Размещения и перестановки Определение 1. Пусть дано конечное множество A, n(A)=n и 1 k n. k-размещением множества A называется любой упорядоченный набор длины k ( ), где все координаты - попарно различные элементы множества A. Число всех k-размещений n-элементного множества обозначается через.

Пример. Пусть A= a,b,c,d. Выпишем все 2-размещения этого четырёхэлементного множества: (a;b), (b;a), (a;c), (c;a), (a;d), (d;a), (b;c), (c;b), (b;d), (d;b), (c;d), (d;c). Таким образом

Теорема 2. Пусть n N, 1 k n. Тогда. Доказательство. Применим индукцию по k. Докажем равенство при k=1. 1-размещения это наборы состоящие из одного элемента, взятого из n-элементного множества. Очевидно, что их будет столько же, сколько элементов, в n-элементном множестве, то есть.

C другой стороны, то есть

Допустим, равенство выполняется для k < n, то есть Докажем равенство для k+1 n. Каждый (k+1)- элементный набор можно получить из k-элементного приписыванием справа одного допустимого элемента. Для фиксированного k-элементного набора это будет любой элемент, не входящий в этот набор. Очевидно, что таких допустимых элементов будет n-k. Значит, из одного k-элементного набора можно получить (n-k) (k+1)- элементных наборов, поэтому

Пример. В первенстве страны участвуют 12 команд. Сколькими способами они смогут занять призовые места. Решение. Поскольку является существенным тот факт, какая команда займет первое место, какая – второе, какая - третье, то задача сводится к вопросу: сколькими способами можно выбрать трёхэлементный упорядоченный набор из 12-элементного множества. Таких способов будет способов.

Замечание 3. При k>n невозможно построить k-размещение, поэтому при k>n. Замечание 4. При k=0 под 0-размещением мы будем понимать пустое множество. Так как пустое множество единственно, то что согласуется с формулой, так как при k=0 имеем

Определение 5. Пусть конечное множество A состоит из n элементов. k -размещением с повторениями множества A называется упорядоченный набор длины k, элементы которого берутся из A. Элементы в k-размещении с повторениями не обязаны быть различными. Пример. Пусть A= { 1,2,3}. Выпишем все 2-размещения с повторениями множества A: (1;1),(1;2),(1;3),(2;1),(2;2),(2;3), (3;1),(3;2),(3;3). Число k-размещений с повторениями n-элементного множества обозначается

Теорема 6. Доказательство. Применим индукцию по k. При k=1 число 1-размещений равно числу элементов множества A, то есть С другой стороны, n 1 =n. Базис индукции доказан. Допустим, формула верна при k=l, то есть

Докажем утверждение при k= l +1. Из каждого упорядоченного l-элементного набора можно получить n упорядоченных наборов длины l+1, приписывая любой элемент A справа, то есть (l +1)-размещений с повторениями в n раз больше, чем l -размещений с повторениями, то есть Теорема доказана.

Пример. Номер машины состоит из двух букв русского алфавита (32 буквы) и из четырёх цифр. Сколько всего существует номеров? Решение. Пару букв мы можем выбрать способами, четвёрку цифр можно выбрать способами. Значит, всего машинных номеров можно составить по принципу произведения

Определение 7. Перестановкой n-элементного множества называется упорядоченный набор длины n, составленный из этих элементов, причём каждый элемент входит в набор ровно один раз. Число перестановок n-элементного множества обозначается символом P n. Пример. Выпишем все перестановки 3-х элементного множества A={a;b;c}: (a;b;c),(a;c;b),(b;a;c),(b;c;a),(c;a;b),(c;b;a). Таким образом, P 3 =6.

Теорема 8. P n =n! Доказательство. Каждую перестановку n-элементного множества можно рассматривать как n-размещение этого множества. Поэтому

Задача. Сколькими способами на шахматной доске можно расставить 8 ладей таким образом, что бы они не били друг друга. Решение. Первую вертикаль можно заполнить лишь одной ладьёй, чтобы не нарушалось условие задачи. Причём количество способов заполнить эту вертикаль равно восьми. На вторую вертикаль можно поставить тоже только одну ладью, причём уже семью способами, и т.д. вплоть до восьмой вертикали, которую можно заполнить одним способами. По принципу произведения всего способов расстановки ладей так, чтобы они не били друг друга, будет 8·7·6·…·2·1=8!

§3.Сочетания. Свойства сочетаний. Бином Ньютона Определение 1. Пусть дано n-элементное множество. Любое k-элементное подмножества множества A называется k-сочетанием n-элементного множества. Число k-сочетаний n-элементного множества обозначается. Пример. Выпишем все 2-сочетания 4-элементного множества A={a,b,c,d}: {a;b},{a;c},{a;d},{b,c},{b,d},{c,d}. Таким образом,.

Теорема 2. при k n. Доказательство. Из одного k-сочетания можно получить k! k- размещений n-элементного множества, потому что k элементов можно упорядочить k! способами. Поскольку каждое k-размещение есть не что иное, как упорядоченное k-сочетание, то всего k-размещений будет С другой стороны k-размещений имеется. Получили равенство или,

и отсюда получаем искомую формулу:

Теорема 3 (простейшие свойства сочетаний). 1) 2) 3) 4) 5), (m 1);

Теорема 4 (бином Ньютона).

Доказательство. Второе равенство представляет собой не что иное, как разные записи одной и той же суммы. Слева стоит эта сумма в развернутом виде, а справа эта же сумма, записанная с помощью знака суммирования. Поэтому доказываем первое равенство. Рассмотрим выражение:

Раскрыв скобки, получим сумму В первой сумме количество слагаемых равно количеству элементов множества то есть. Во второй сумме количество слагаемых равно количеству двухэлементных подмножеств n-элементного множества S, то есть равно.

Число слагаемых в k-ой сумме равно количеству k-элементных подмножеств n-элементного множества S, то есть равно Поэтому, если положить в A то получим Теорема доказана

Следствие 5. Следствие 6. Следствие 7. (a+b) n =

Замечание. В силу большой важности бинома Ньютона для самых разных разделов математики, числа называются биноминальным коэффициентами. Следствие 9.

Определение 10. Пусть А = {a 1, a 2, …, a n } - n–элементное множество. k-сочетанием с повторениями множества А называется неупорядоченный набор [a 1,a 2,…,a k ], где все элементы принадлежат множеству А, причем допустимо повторение этих элементов. Пример. Пусть А = {a, b, c}. Выпишем все 2-сочетания с повторениями множества А : [a, a], [a, b], [a, c], [b, b], [b, c], [c,c]. Число k–сочетаний с повторениями n-элементного множества обозначается. Приведенный пример показывает, что

Лемма. Число всех упорядоченных нулей и единиц последовательностей из нулей и единиц длины n, в которых присутствует l нулей, равно (или, что одно и то же).

Теорема 12.. Пример. В магазине продаются пирожные 4 сортов. Сколькими способами можно купить 8 пирожных? Решение. Находим число 8-сочетаний с повторениями 4-х элементного множества: