Материал: erovenko_va_osnovy_vysshei_matematiki_dlia_filologov

го множества, содержащего n элементов? Сейчас мы можем записать ее короче: сколько существует размещений из n элементов по m?

Число всевозможных размещений из n элементов по m обозначают символом Anm (A — первая буква французского слова arrangement — разме-

щение). Читается: «Число размещений из эн элементов по эм» или «А из эн по эм».

Утверждение. Число размещений Anm, ãäå m n, можно вычислить по формуле:

Доказательство. Рассмотрим множество из n элементов. Первое место в размещении, состоящем из m элементов, можно занять любым из n элементов множества. Оставшиеся m–1 мест упорядоченного множества можно занять некоторым размещением из оставшихся n–1 элементов по m–1 элементов. Число таких размещений равно Anm 11 (по определению

Anm 11). Таким образом, размещение из n ïî m можно рассматривать как

пару, состоящую из одного элемента, выбранного из n элементов заданного множества, и размещения из n–1 элементов по m–1, оставшихся после выбора первого элемента. В силу комбинаторного принципа умножения

87

число всех таких пар или число всех размещений из n ïî m равно n Anm 11, т. е. мы доказали равенство вида

Anm n Anm 11 .

Из этой формулы последовательно получим:

Anm = n Anm 11 = n (n – 1) Anm 22 =

= n (n – 1) (n – 2) Anm 33 = … = n (n – 1) (n – 2) … (n – m + 1).

Но произведение m последовательных убывающих натуральных чисел от n äî n – m + 1 равно отношению факториалов чисел n è n – m, ò. å.

Поэтому получаем окончательную, искомую нами формулу для числа перестановок из n ïî m:

Очевидно, что дробь, стоящая в правой части этой формулы, сокращается и равна целому числу. В частности, из формулы числа размещений следует:

êó существует только одно пустое множество и можно считать, что

оно может быть упорядочено одним-единственным образом. Кроме того, это логично: есть единственный способ не выбирать ни одного объекта из n имеющихся — ничего не делать.

Замечание. Перестановки — это частный случай размещений при m = n, т. е. Ann = Pn = n!. Кроме того, для m = n–1 в формуле для числа размещений имеем Ann 1 = Ann = n!.

Последнее равенство только на первый взгляд удивительно. В действительности, если из n различных объектов выбраны n–1 и расположены в некотором порядке, то на оставшееся место может претендовать только один оставшийся элемент, который можно и не выбирать, т. е. действительно Ann = Ann 1.

88

Пример. Посчитаем, сколько существует в n-буквенном алфавите m-буквенных слов, состоящих из различных букв. По формуле для размеще-

n!

.

(n m)!

В этой формулировке мы для краткости говорим «n-буквенный алфавит» вместо слов «множество, содержащее n элементов» è «m-буквенное слово» вместо слов «упорядоченное множество из m элементов». Кроме того, слова здесь имеют иной смысл, чем в филологии, — допускаются, например, такие «слова», как абвгд, т. е. мы будем иметь дело со «словами» в некотором фиксированном «алфавите». Например, в качестве «букв» такого алфавита могут выступать числа, например, 1, 2, …, n. Удобная алфавит- но-буквенная терминология не меняет сути дела в комбинаторных задачах, так как элементы конечного множества всегда можно перенумеровать.

Например, из 33 букв русского алфавита можно составить всего

различных двухбуквенных слов, не содержащих повторений букв.

Пример. Студенту необходимо пересдать 3 экзамена на протяжении 6 дней. Посчитаем, сколько теоретически существует вариантов для

дней сдачи этих экзаменов.

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

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

ïðîñ: сколькими способами можно выбрать из n различных предметов m

øòóê (m n)?

Например, пусть из четырех корзин, обозначенных буквами А, Б, В, Г нужно выбрать две. Сколькими способами это можно сделать? Свяжем этот пример с примером, рассмотренным выше, а именно выбранные корзины будем отмечать тем, что положим в них шары. Тогда дерево вариантов, изображенное на рис. 2.2, дает первый шаг решения. Однако можно заметить, что каждый выбор пары корзин встречается в списке из 12 соответствующих размещений дважды, например, АБ и БА. Сейчас для нас не существенно, какой шар, первый или второй оказался в корзине, или, другими словами, в каком порядке осуществлялся выбор корзин. Поскольку в нашем случае перемен мест двух выбранных корзин, т. е. перестановок, всего две, то две корзины из четырех можно выбрать 12:2 = 6 способами.

89

Пример. Пусть имеется две гласные и три согласные фонемы. Рассмотрим, сколько можно построить пятифонемных «слов», отличающихся

друг от друга только расположением гласных и согласных фонем.

Задача сводится к выбору, например, двух позиций из пяти, на которых могут находиться гласные фонемы. С учетом порядка число таких раз-

мещений равно 4 5 = 20, а так как нас интересует только, на каких позициях расположены две гласные фонемы без учета их порядка, то окончательно имеем 20:2 = 10 пятифонемных «слов».

Определение сочетания. Конечные (неупорядоченные) множества

называют сочетаниями.

Отметим, что перестановки и размещения — это упорядоченные множества, а сочетание — это неупорядоченные множества. Сочетания — это

такая выборка элементов, при которой их порядок совершенно не важен.

Рассмотрим, например, все подмножества трехбуквенного множества {А, Б, В}. Таких подмножеств заданного множества всего восемь. Пере- числим их: — пустое множество; {А}, {Б}, {В} — три множества по 1 элементу в каждом; {А, Б}, {А, В}, {Б, В} — три множества по 2 элемента в каждом; множество {А, Б, В}, состоящее из 3 элементов.

Число всевозможных сочетаний из n элементов по m обозначают символом Cnm (С — первая буква французского слова combinaison — сочетание).

Читается: «Число сочетаний из эн элементов по эм» или «Цэ из эн по эм».

Утверждение. Число сочетаний Cnm, где m n, можно вычислить по формуле

Доказательство. Будем основываться на том, что нам известно о перестановках и размещениях. Будем для краткости писать «k-элементное

множество (подмножество)» вместо слов «множество (подмножество), содержащее k элементов». Из каждого m-элементного подмножества (сочетания) n-элементного множества получается Pm упорядоченных множеств, состоящих из тех же элементов, из которых состоит взятое подмножество. Следовательно, число Anm всех упорядоченных m-элементных ïîä-

90

Дадим другое, непосредственное, доказательство последней формулы этого равенства. Если из n-элементного множества отобраны m элементов, то их можно занумеровать номерами 1, 2, 3, …, m всего m! способами. Оставшиеся n–m элементов можно занумеровать номерами m+1, m+2, …, n всего (n – m)! способами. Кроме того, сам отбор m элементов из n можно произвести Cnm способами. Таким обра-

зом, мы получили m!(n – m)!· Cnm вариантов нумераций полного множества из n элементов, которых всего n!. Поэтому m!(n – m)!· Cnm = n! или

что и требовалось доказать.

Формула числа сочетаний интересна уже тем, что дробь, стоящая в ее правой части, равна целому числу, т. е. все числа, стоящие в знамена-

теле, сократятся с числами, стоящими в числителе. В частности, из формулы числа сочетаний следует:

венство имеет содержательный смысл, состоящий в том, что есть толь-

ко один способ не выбирать ни один элемент (или выбрать 0 элементов)

из n-элементного множества. В частности, отметим, что Cnn = 1.

Замечание. Обратим внимание на своеобразную симметричность формулы для числа сочетаний: если заменить m на m–n, то получится то же самое выражение, только факториалы в знаменателе поменяются местами:

Cnm = Cnn−m .

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

91