Материал: erovenko_va_osnovy_vysshei_matematiki_dlia_filologov

Поэтому число способов, которым можно выбрать m человек из n, равно числу способов, которым можно выбрать n – m человек из n. Это означает, что Cnm = Cnn−m или непосредственно имеем

Замечание. Укажем на важную зависимость между сочетаниями для 0 ≤ m < n, которую называют иногда тождеством Паскаля:

Cm+ = Cm + Cm−1 .

n 1 n n

Например, пусть в группе учится n+1 студентов. Отметим старосту группы. Разобьем всевозможные подгруппы по m человек на два множества, а именно на те, в которые староста входит, и на те, в которые староста не входит. Посчитаем, сколько подгрупп в первом множестве. Так как один человек в них зафиксирован, то к нему добавляется разными способами еще m–1 человек из оставшихся n. Значит в первом множестве Cnm−1 подгрупп. Во втором множестве выбираются подгруппы по m человек из n человек группы, так как староста не рассматривается. Их

число равно Cnm . Но Cnm+1 — это общее число подгрупп тех, в которые староста входит, и тех, в которые староста не входит. Следовательно,

рии вероятностей. Например, из тождества Паскаля Cnm+1 + Cnm = Cnm++11

следует, что для всех натуральных чисел n и m, 0 ≤ m < n, справедливо равенство

Cm + Cm+ + … + Cm = Cm++1 .

m m 1 n n 1

Для m = 1 это известная формула суммы первых n членов арифметической прогрессии:

1 + 2 + … + n = n(n + 1) . 2

92

Замечание. Для любых подмножеств A1, A2, …, Am справедливо общее правило подсчета числа элементов объединения множеств

A1 A2 … Am, называемое формулой включений и исключений:

n(A1 A2 … Am) = n(A1) + n(A2) + … + n(Am) – n(A1 ∩ A2) –

–n(A1 ∩ A3) – … – n(Am-1 ∩ Am) + n(A1 ∩ A2 ∩ A3) + n(A1 ∩ A2 ∩ A4) + … +

+n(Am-2 ∩ Am-1 ∩ Am) + … + (–1)m–1n(A1 ∩ A2 … ∩ Am).

В частности, если n(A1) = n(A2) = … = n(Am) = n1, n(A1 ∩ A2) = … = = n(Am-1 ∩ Am) = n2, …, n(A1 ∩ A2 … ∩ Am) = nm, то по этому замечанию из

формулы включений и исключений получим, что

n(A1 A2 … Am) = ∑m (−1)k−1Cmk nk .

k=1

Замечание. Отметим еще одно использование числа сочетаний. Для произвольных чисел a и b и произвольного натурального числа n справедлива формула бинома Ньютона:

(a + b)n = Cn0 an + Cn1 an–1b + … + Cnm an–mbm + … + Cnn−1 abn–1 + Cnn bn =

n

= ∑Cnk an-k bk . k =0

Само название «бином Ньютона» многим знакомо благодаря роману Михаила Булгакова «Мастер и Маргарита». Небезызвестный Коровьев говаривал: «Подума-

ешь, бином Ньютона». Он, возможно, имел в виду, что для него это не проблема. Но что же, собственно, это такое?

Биномом (или в переводе с латыни двучленом) называют сумму двух слагаемых, например, a + b. Хорошо известна формула для квадратного бинома: (a + b)2 = a2 + 2ab + b2. Аналогичная формула для (a + b)n в случае произвольного натурального n называется биномом Ньютона и имеет прямое отношение к комбинаторике. Эта формула носит имя английского физика и математика Исаака Ньютона, хотя она была известна задолго до него, например, в Европе ее знал французский математик и философ Блез Паскаль. Заслуга Ньютона состоит в том, что он нашел обобщение этой формулы на случай нецелых показателей. Тем не менее приведенное выше разложение называют обычно биномом Ньютона, а

коэффициенты Cnm называются биномиальными коэффициентами. На-

93

пример, если положить в этой формуле n = 3, 4 и 5, то получим следующие разложения:

(a + b)3 = a3 + 3a2b + 3ab2 + b3,

(a + b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4,

(a + b)5 = a5 + 5a4b + 10a3b2 + 10a2b3 + 5ab4 + b5.

В частности, если положить в формуле бинома Ньютона a = b = 1, то получим равенство

Cn0 + Cn1 + Cn2 + … + Cnn = 2n.

Укажем на некоторые следствия из формулы бинома Ньютона:

1.Сумма показателей степени при a и b в любом слагаемом разложения равна n.

2.Биномиальные коэффициенты, равноудаленные от концов разложения, равны

между собой, так как Cnm = Cnn−m .

3. Биномиальные коэффициенты сначала возрастают, а затем убывают.

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

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

C43 = C41 = 3!1!4! = 4 способами можно выбрать эти три слова:

быть очень знаменитым, быть очень некрасиво, быть знаменитым некрасиво, очень знаменитым некрасиво.

Пример. Посчитаем, сколько карточек лотто-миллион нужно купить и заполнить, чтобы на них оказались все комбинации по 6 номеров из 49 возможных.

Нужное количество карточек равно числу сочетаний из 49 элементов по 6, т. е. всего их

а это составляет почти 49 млн карточек. Мораль проста: для реализации подобной идеи уже надо быть миллионером.

94

Заметим, что если на карточке угадано 5 номеров, то это значит, что из 6 выпавших номеров могут быть вычеркнуты любые 5 из них, а из остальных 43 номеров — только 1. Поэтому в силу комбинаторного принципа умножения число способов угадать 5 номеров выигрышного тиража равно C65 C431 . Точно также карточек с совпавшими 4 номерами тео-

ретически может быть C64 C432 .

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

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

Вопросы для самоконтроля

1.Верно ли, что вершины нарисованного на плоскости правильного пятиугольника можно буквами А, Б, С, Д, Е обозначить 120 способами?

2.Верно ли, что если есть материи шести различных цветов, то трехцветный флаг с горизонтальными полосами одинаковой ширины можно сделать 120 способами?

3.Верно ли, что если 5 ≤ n < 9, то для сочетаний справедливо неравенство Cn5 < Cn4 , если n = 9, то справедливо равенство Cn5 = Cn4 , наконец,

если n > 9, то справедливо неравенство Cn5 > Cn4 ?

2.3. КОМБИНАТОРИКА: ВЫБОР С ПОВТОРЕНИЯМИ

Одна из особенностей комбинаторики заключается в том, что в ней исключительно большую роль играет точная формулировка задачи. Большинство ошибок связано с некорректными постановками задач изза неопределенности формулировок. Когда речь идет о подсчете числа студентов в группе никакой неопределенности не возникает. Менее определенная ситуация возникает, когда посчитать нужно число вариантов или способов. Некоторая расплывчатость понятия: «о числе вариантов» связана с тем, что варианты — это умозрительные понятия и их нельзя увидеть непосредственно, если нет полного перечня различных вариан-

95

тов, описанных с помощью математических символов. Рассмотрим сле-

дующий вопрос:

Сколькими способами можно распределить три шоколадки между тремя девушками?

Решение зависит от выбранного способа понимания этой задачи. В зависимости от этого возможны, например, пять разных ответов на поставленный вопрос, а именно 1, 3, 6, 10, 27.

Один из источников неопределенности заключается в слове «распределить». Пусть, например, все шоколадки одинаковые. Социальносправедливый вариант распределения дает 1 вариант типа (1,1,1), т. е. когда каждой девушке достается шоколадка. Если все шоколадки отданы одной девушке, то получим 3 варианта типа (3,0,0), (0,3,0), (0,0,3). Наконец, если понимать «распределить» в широком смысле, то можно доба-

вить еще 6 вариантов типа (2,1,0), (2,0,1), (1,2,0), (1,0,2), (0,2,1), (0,1,2).

Таким образом, «распределения» дают 10 различных вариантов. Если дополнительно предположить, что все шоколадки различные, то можно получить максимальное число «распределения» — 27 вариантов.

Главное правило комбинаторики: прежде чем подсчитывать чис-

ло различных вариантов, необходимо точно выяснить смысл слов «различные варианты».

Заметим, что если число вариантов не слишком велико, то его можно найти прямым перебором этих вариантов. Сцилла и Харибда комби-

наторных подсчетов — не пропустить ни один вариант и ни один из них не посчитать дважды. Рассмотрим модельную задачу на тему «пе-

рестановки с повторениями», которую нельзя непосредственно решить с помощью формул подсчета вариантов «перестановки без повторений», рассмотренных в предыдущем разделе.

Пример. Посчитаем число анаграмм слова БАОБАБ.

Напомним, что комбинаторика позволяет считать словом любую комбинацию букв. Математики любят сводить новые задачи к уже решенным задачам. Для того чтобы воспользоваться способом подсчета числа перестановок, применим новый для нас прием растождествления. Он показывает, как можно переходить от одного понятия «различия» к другому. При точном понимании терминов, т. е. при соблюдении главного правила комбинаторики, можно открыть дополнительные возможности решения комбинаторных задач. Слово растождествление вряд ли есть в словарях, но оно достаточно точно передает суть дела. Суть его в том, чтобы рассматривать одинаковые буквы слова как различные, например, с помощью их индексации.

96