Дискретная математика. Методичка. Кацаран

чисел 1, 2, . . . , n + k − 1 по k .

Неупорядоченная k -выборка [ai1 , ai2 , . . . , aik ] однозначно определяется комбинацией из номеров ее элементов [i1, . . . , ik ] Ink . Не ограничивая общности рассуждений, можно считать, что i1 ≤ i2 ≤ . . . ≤ ik . По-

ложим, j1 = i1 , j2 = i2 + 1 , jk = ik + k −1 , тогда js {1, 2, . . . , n + k −1} для s = 1, k и выборка {j1, j2, . . . , jk } Jnk+k−1 .

Пусть {j10, j20, . . . , jk0} произвольная комбинация из Jnk+k−1 , так как она не зависит от порядка расположения элементов, то можно счи-

Мы установили взаимооднозначное соответствие между множествами Ink и Jnk+k−1 , откуда следует, что их мощности совпадают

|Ik | = |J k+ −1|, т. е. Hk = Ck+ −1.

n n k n n k

Теорема доказана.

§ 5. Перестановки с повторениями. Подсчет числа беспорядков

Классическая задача комбинаторики о числе разбиений с повторениями формулируется следующим образом: сколькими способами можно разбить n различных предметов на k групп по n1 предметов в первой группе, n2 во второй группе, . . . , nk в последней группе?

Такие комбинации называются перестановками с повторениями.

Число различных перестановок из n1 предметов первого вида, n2 предметов второго вида, . . . , nk предметов k -го вида вычисляется по

формуле:

P (n1, n2, . . . , nk) = (n1 + n2 + . . . + nk )! . n1!n2! . . . nk !

Действительно, для первой группы можно выбрать n1 предметов из n = n1 + n2 + . . . + nk имеющихся в наличии Cnn1 способами. Для второй группы n2 предметов из (n −n1) оставшихся в наличии Cnn−2 n1 способами. Для третьей группы n3 предметов из (n −n1 −n2) оставшихся в наличии Cnn−3 n1−n2 способами. Этот процесс продолжается вплоть до последней группы. Общее число разбиений, которое мы будем обозначать

P (n1, n2, . . . , nk) , равно:

31

Таким образом, число разбиений обобщает число сочетаний. Действительно, если мы разбиваем n предметов на две группы, то

n1 + n2 = n , откуда n2 = n − n1 и

Рассмотрим еще один вид перестановок n предметов циклические перестановки.

Задача заключается в следующем: рассматриваются n предметов, расположенных не в ряд, а по кругу. В этом случае перестановки считаются одинаковыми, если они получаются при переходе друг в друга при вращении, т. е. при циклическом сдвиге. Число таких перестановок из

e e

различных предметов P (n) равно: P (n) = (n − 1)! .

Немаловажной является и задача о подсчете числа беспорядков , когда требуется найти число N перестановок из цифр {1, 2, . . . , n}, таких, что никакая цифра не остается на своем месте. Число таких перестановок находится по формуле:

N = n! Xn (−1)k k1! .

k=0

§ 6. Свойства сочетаний. Бином Ньютона

При помощи формулы (3.2) посредством алгебраических преобразований легко получить следующие свойства сочетаний:

j=0

Докажем его, пользуясь методом математической индукции. При n = 1 имеем очевидное равенство:

X1

x + a = C1j xj a1−j = a + x.

j=0

32

Предположим, что равенство (3.3) имеет место при n = k и, исходя из этого предположения, докажем его для случая n = k + 1 :

Xk

= Ck0+1 ak+1 + (Cki−1 + Cki ) xi ak+1−i + Ckk+1+1 xk+1 a0 = i=1

Xk+1

=Cki +1 xi ak+1−i.

i=0

Из равенства (3.3), положив сначала x = a = 1 , затем x = (−a) = 1 , получим новые свойства сочетаний:

собой k -элементное подмножество множества мощности n , то величина

P

с этим из свойства 5) сочетаний получаем теорему о мощности булеана (см. стр. 10).

§ 7. Общий случай формулы включений и исключений

Пусть имеется N элементов, каждый из которых может обладать или не обладать свойствами α1 , α2 , . . . , αn . Через N (αi, αj , . . . , αk ) обозначается количество элементов, обладающих свойствами αi , αj , . . . , αk . Если необходимо подчеркнуть, что берутся элементы, заведомо не обладающие некоторым свойством, то это свойство пишется с чертой; например, N (α1, α2) количество элементов, не обладающих свойством α1 и обладающих свойством α2 .

Задача состоит в том, чтобы найти N (α1, . . . , αn) количество элементов, не обладающих ни одним из свойств α1 , α2 , . . . , αn .

Для решения этой задачи в случае трех свойств воспользуемся следующим выражением для мощности объединения множеств A , B и C :

|A B C| = |A|+|B|+|C|−|A∩B|−|A∩C|−|B ∩C|+|A∩B ∩C|. (3.4)

33

Обозначим через A , B , C множества элементов, обладающих свойствами α1 , α2 , α3 соответственно, тогда

|A| = N (α1), |B| = N (α2), |C| = N (α3),

|A ∩ B| = N (α1, α2), |A ∩ C| = N (α1, α3), |B ∩ C| = N (α2, α3),

|A ∩ B ∩ C| = N (α1, α2, α3).

На приведенном рисунке множество элементов, изображенное в виде прямоугольника, имеет мощность N . Множество элементов, не обладающих ни одним из свойств (его мощность равна N (α¯1, α¯2, α¯3) ), представлено заштрихованной частью прямоугольника. Исходя из того, что N (α¯1, α¯2, α¯3) = N − |A B C| и используя равенство (3.4), получим формулу включений и исключений для случая трех свойств:

N (α¯1, α¯2, α¯3) = N − N (α1) − N (α2) − N (α3)+

+N (α1, α2) + N (α1, α3) + N (α2, α3) − N (α1, α2, α3).

Теорема. При сделанных ранее предположениях и обозначениях формула включений и исключений для случая n свойств имеет вид:

Доказательство. Следует отметить, что алгебраическая сумма

X

N (αi1 , . . . , αis )

1≤i1<...<is≤n

в (3.5) распространена на все сочетания свойств из множества α1, . . . , αn по s , причем, знак плюс ставится, если число s учитываемых свойств четно, и знак минус, если это число нечетно.

34

Доказательство равенства (3.5) будем проводить методом математической индукции по числу n свойств. В случае n = 1 равенство (3.5) приобретает вид: N (α1) = N − N (α1) . Оно верно, так как каждый элемент либо обладает свойством α1 , либо не обладает. Далее пусть

N (α1, . . . , αn−1) = N − N (α1) − . . . − N (αn−1) + N (α1, α2) + . . .

. . . + N (αn−2, αn−1) − N (α1, α2, α3) − . . . − N (αn−3, αn−2, αn−1) + . . .

. . . + (−1)n−1N (α1, α2, . . . , αn−1). (3.6)

Это равенство верно для любого конечного множества элементов, в частности для множества элементов, обладающих свойством αn . Общее количество этих элементов равно N (αn) . Число N (α1, . . . , αn−1, αn) элементов, не обладающих (n − 1) свойством на множестве элементов, обладающих свойством αn , вычисляется по формуле, которая следует из (3.6):

N (α1, . . . , αn−1, αn) = N (αn) − N (α1, αn) − . . . − N (αn−1, αn)+

+N (α1, α2, αn)+. . .+N (αn−2, αn−1, αn)+. . .−(−1)n−1N (α1, . . . , αn−1, αn).

В каждом слагаемом здесь присутствует αn . Вычтем это равенство из (3.6). В левой части результата получим выражение:

N (α1, . . . , αn−1) − N (α1, . . . , αn−1, αn) = N (α1, . . . , αn−1, αn),

а в правой части, сгруппировав слагаемые с одинаковым количеством свойств, получим правую часть равенства (3.5). Теорема доказана.

§ 8. Частный случай формулы включений и исключений

Предположим, что число N (αi1 , . . . , αis ) элементов, обладающих свойствами αi1 , . . . , αis , не зависит от характера свойств, а зависит от их числа, т. е. пусть

N (αi) = N (1), i {1, . . . , n}, N (αi, αj ) = N (2), i, j {1, . . . , n},

N (αi1 , . . . , αis ) = N (s), i1, . . . is {1, . . . , n}.

Используя введенные обозначения, получим следующие выражения для сумм в (3.5):

35

k=0

§ 9. Применение формулы включений и исключений

Рассмотрим множество чисел {1, 2, . . . , n} и найдем число D(n) перестановок (ai1 , . . . , ain ) этих чисел, в которых ни одно из них не остается на своем первоначальном месте ai =6 i , i = 1, n .

Обозначим через αi свойство перестановки, заключающее в том, что число i стоит на своем месте, а через N (αi) обозначим количество перестановок, обладающих этим свойством.

Нетрудно заметить, что N (αi) = (n − 1)! , i {1, . . . , n}. Пусть N (αi1 , . . . , αik ) количество перестановок, в которых числа αi1 , . . . , αik стоят на своих местах, тогда

N (αi1 , . . . , αik ) = (n − k)!.

Здесь мы имеем тот случай, когда величины N (αi1 , . . . , αik ) не зависят от характера свойств, а зависят только от их числа:

N 1 = (n − 1)!, . . . , N k = (n − k)!.

Число элементов N в рассматриваемом случае равно числу перестановок из n элементов: N = N 0 = n! . Подставляя найденные значения для N k , k = 0, n , а также выражения для Cnk в формулу (3.7), получим равенство

D(n) = n! n (−1)k . (3.8)

X

k=0

k!

В случае n = 3 из (3.8) находим, что число D(3) перестановок, в которых числа 1, 2, 3 не стоят на своих местах, равно 2.

§ 10. Рекомендации к решению задач

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

36

Добавим, что при решении задач комбинаторики можно пользоваться терминологией: элементы (объекты), из которых состоит k - выборка, помещаются в ячейки . Порядок заполнения ячеек может быть произвольным, но нужно выбирать наиболее простой.

Пример 1. Сколько есть трехзначных чисел, делящихся на 4, в записи которых не используются цифры 0, 4, 5, 6, 8, 9?

Решение. Число делится на 4 тогда и только тогда, когда две последние его цифры образуют число, делящееся на 4. В нашем случае это числа 12, 32, 72. Для построения комбинации понадобятся две ячейки : в первую можно поместить одну из цифр 1, 2, 3, 7; во вторую одну из ранее перечисленных двухзначных чисел. Первый объект можно выбрать 4 способами, второй объект 3 способами. По правилу произведения ответом на поставленный вопрос является число 4 · 3 = 12 .

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

Пример 2. Сколько есть шестизначных чисел, в каждом из которых нет одинаковых цифр, а вторая и четвертая цифры нечетны?

Решение. Очевидно, что надо взять шесть ячеек . Заполним эти

ячейки . В первую ячейку поместим одну любую из 9 цифр (кроме

0 ). Во вторую ячейку нужно поместить нечетную цифру. Так например, если на первое место мы поставили цифру 2, то на второе место можно поставить одну из цифр 1 , 3 , 5 , 7 или 9 . Если же на первом месте уже стоит цифра 9 , то на второе место можно поставить только 1 , 3 , 5 или 7 . Указанный способ выбора является неудобным, поэтому рассмотрим другой порядок заполнения

ячеек : вторая, четвертая, первая, третья, пятая, шестая. Во вторую поместить одну из 5 нечетных цифр, в четвертую любую из 4 оставшихся нечетных цифр, в первую одну из 7 (кроме 0 и тех двух, что уже стоят, в третью любую из 7 оставшихся, в пятую любую из 6 оставшихся, в шестую любую из 5 оставшихся. В результате получим 5 · 4 · 7 · 7 · 6 · 5 = 29 400 чисел, обладающих заданным свойством.

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

Пример 3. Сколько есть пятизначных чисел, в записи которых есть хотя бы одна четная цифра?

Решение. Всего пятизначных чисел 9 ·10 ·10 ·10 ·10 = 90 000 , из них

37

5 · 5 · 5 · 5 · 5 = 3125 чисел, которые состоят только из нечетных цифр. Поэтому количество требуемых чисел равно 86 875 .

Разберем типичные задачи на применение правила суммы и формулы включений и исключений.

Пример 4. Сколькими способами из 28 костей домино можно выбрать кость, на которой есть 1 или 6 ?

Решение. Выбрать кость, содержащую 1 , можно семью способами, содержащую 6 тоже семью способами, но среди этих способов есть один общий это выбор кости 1 : 6 . В соответствии с правилом суммы общее число способов нужной кости можно осуществить 7 + 7 − 1 = 13 способами.

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

Решение. Нужно найти число 3-выборок из 6 элементов без повторений (так как все цвета различны). Порядок, в котором располагаются выбранные цвета, существенен. Следовательно, нужно найти число упорядоченных выборок, т. е. число размещений из 6 по 3 без повторений:

Данную задачу можно решить и другим способом. Для выбора цвета первой полосы имеется 6 вариантов. После произведенного выбора цвет для второй полосы можно выбрать 5 из оставшихся 5 способов. Далее выбираем цвет для третьей полосы из 4 оставшихся 4 способами. По правилу произведения имеем: 6 · 5 · 4 = 120 способов.

Пример 6. Сколько существует различных наборов длины 10 из нулей и единиц?

Решение. Так как набор состоит из десяти элементов, которые принимают только два возможных значения 0 или 1 , то в этом наборе будут присутствовать одинаковые значения элементов (т. е. элементы повторяются). Следовательно, нужно найти число упорядоченных выборок

7 торговых марок. Сколькими способами можно купить: а) 5 аппаратов разных торговых марок; б) 4 аппарата; в) 15 аппаратов?

Решение. В случае а) нужно подсчитать число неупорядоченных 5- выборок из 7 возможных без повторений (все телефонные аппараты разных торговых марок). Их число определяется по формуле:

38

В случаях б) и в) нас интересуют неупорядоченные выборки из 7 элементов с повторениями длины 4 и 15 соответственно. Их значения определяются по формулам:

Пример 8. Семь девушек водят хоровод. Сколькими различными способами они могут встать в ряд?

Решение. Если девушки стояли бы на месте, то получилось бы 7! способов перестановок в ряду. Но так как они кружатся, то их положение относительно окружающих предметов несущественно, а важно только их взаимное расположение. Поэтому перестановки, переходящие друг в друга при кружении (циклическом сдвиге), нужно считать одинаковыми. Так как из каждой перестановки сдвигом можно получить еще 6 новых, то количество интересующих нас перестановок будет равно: 7!/7 = 6! .

Пример 9. В ходе экзаменационной сессии 1 студентов получили оценки отлично , 12 хорошо , 13 удовлетворительно , 5хорошо и отлично , 7 хорошо и удовлетворительно , 8отлично и удовлетворительно . У трех студентов все виды оценок. Сколько студентов в группе, если известно, что все они сдали сессию? Сколько отличников в группе? Сколько в группе чистых троечников ?

Решение. В условии задачи n1 = 12 , n2 = 12 , n3 = 13 , n12 = 5 , n13 = 8 , n23 = 7 , n123 = 3 . По формуле для правила суммы трех объектов находим общее число студентов в группе:

12 + 12 + 13 − 5 − 8 − 7 + 3 = 20 ; число отличников в группе равно:

n1 − (n12 + n13) + n123 = 12 − (5 + 8) + 3 = 2 ; число чистых троечников равно:

n3 − (n13 + n23) + n123 = 13 − (8 + 7) + 3 = 1 .

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

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

39

Пример 10. Имеются предметы k сортов: n1 предметов одного сорта, n2 предметов другого сорта, . . . , nk предметов k -го сорта, где все предметы одного сорта все же различны друг от друга. Найти число перестановок этих предметов, в которых все предметы одного и того же сорта стоят рядом.

Решение. Из данных k сортов (блоков) можно сделать P (k) = k! перестановок. Но еще можно переставить предметы внутри блоков

n1! , n2! , . . . , nk ! способами. Далее по правилу произведения имеем

n1! · n2! · . . . · nk ! · k! перестановок.

Пример 11. Сколькими способами можно переставить буквы словаперелет так, чтобы три буквы е не шли подряд?

Решение. Объединим все буквы е в один блок еее . Число

P (5) = 5! = 120 . Всего же перестановок с повторениями из букв дан-

ного слова можно составить P (3, 1, 1, 1, 1) = 3+1+1+1+1 = 840 . Значит,

3! 1! 1! 1! 1!

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

N = 840 − 120 = 720 .

Пример 12. Сколькими способами можно расставить m нулей и k единиц, где k ≤ m + 1 , так, чтобы никакие две единицы не стояли рядом?

Решение. Выпишем сначала m нулей. Для единиц получается m+ 1 место (одно место слева, m − 1 в промежутках между нулями и одно справа). На любые из этих m + 1 мест можно поставить одну из k единиц. Это можно осуществить Cmk +1 способами. Если условие k ≤ m + 1 не будет выполняться, то в результате расстановки две единицы в любом случае будут стоять рядом.

Пример 13. Найти число способов разбиения n одинаковых предметов по k урнам ( n и k произвольные натуральные числа).

Решение. Переименуем урны, расположив их в ряд. Между ними будет (k − 1) промежуток. Поставим в соответствии каждому разбиению предметов по урнам последовательность из нулей и единиц следующим образом: сначала последовательность имеет группу из 0 , число которых равно числу предметов в первой урне, затем ставим одну перегородку, обозначив ее за 1 ; далее столько 0 , сколько предметов во второй урне, и опять ставим 1 ; затем столько 0 , сколько в третьей урне, и т. д., заканчивается последовательность группой 0 ; их столько, сколько предметов в последней урне. Следовательно, в такой последовательности будет n нулей и (k − 1) единиц, всего (n + k − 1)

40