Материал: erovenko_va_osnovy_vysshei_matematiki_dlia_filologov

Для четырех букв А, Б, В и Г, добавляя букву Г либо спереди, либо сзади, либо между имеющимися буквами, получим 24 разные последовательности этих букв, которые можно записать в виде следующих упорядоченных множеств:

(À, Á, Â, Ã), (À, Á, Ã, Â), (À, Â, Á, Ã), (À, Â, Ã, Á), (À, Ã, Á, Â), (À, Ã, Â, Á), (Á, À, Â, Ã), (Á, À, Ã, Â), (Á, Â, À, Ã), (Á, Â, Ã, À), (Á, Ã, À, Â), (Á, Ã, Â, À), (Â, À, Á, Ã), (Â, À, Ã, Á), (Â, Á, À, Ã), (Â, Á, Ã, À), (Â, Ã, À, Á), (Â, Ã, Á, À), (Ã, À, Á, Â), (Ã, À, Â, Á), (Ã, Á, À, Â), (Ã, Á, Â, À), (Ã, Â, À, Á), (Ã, Â, Á, À).

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

ÀÁÂ ÀÂÁ ÂÀÁ ÂÁÀ ÁÂÀ ÁÀÂ.

Опредåление перестановки. Установленный в конечном множестве

порядок называют перестановкой его элементов.

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

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

Для сокращения записи произведения всех натуральных чисел от 1 до n в математике используется n-факториал, который обозначают n! (читают

def

«эн-факториал»), т. е. n! 1 2 3 (n–1) n.

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

Число всевозможных перестановок множества из n элементов обозна- чают символом Pn (P — первая буква французского слова permutation — перестановка). Читается: «Число перестановок из эн элементов» или «Пэ из эн».

Утверждение. Число перестановок Pn множества из n элементов можно вычислить по формуле:

Pn = n(n – 1) … 3 2 ! n!

Доказательство. Рассмотрим множество из n элементов. На первое место можно поставить любой из n элементов множества. Если он уже выбран, то останется n – 1 элементов. Оставшиеся n – 1 мест занимает некото-

82

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

Pn = n Pn–1.

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

Pn = n Pn–1 = n (n – 1) Pn–2 = … = n (n – 1) (n – 2) … 2 1.

Таким образом, формула для числа перестановок доказана.

В частности, из определения n! видно, что факториалы двух натуральных ближайших чисел n + 1 è n связаны формулой

(n + 1)! = n! (n + 1).

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

1!= 1, 2!=1! 2 = 2, 3!=2! 3 = 6, 4!=3! 4 = 24, 5!=4! 5 = 120, 6!=5! 6 = 720, 7!=6! 7 = 5040, 8!=7! 8 = 40 320, 9!=8! 9 = 362 880, 10!=9! 10 = 3 628 800.

Отметим, что для вычисления суммы первых n натуральных чисел можно воспользоваться простой формулой суммы первых n членов ариф-

метической прогрессии, ò. å. 1 + 2 + 3 + … + n n(n 1). Для произведения

2

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

Замечание. Выбор для обозначения n! восклицательного знака, возможно, связан с тем, что даже для сравнительно небольших значений n число n! очень велико!

Заметим также, что если в равенство (n + 1)! = n! (n + 1) подставить n = 0, то получится 1! = 0! 1. Поэтому принято считать, ÷òî 0! = 1, поскольку это соглашение часто оказывается удобным в различных общих математических формулах.

Пример. Рассмотрим, сколькими способами можно реализовать перестановку слов знаменитой фразы Бориса Пастернака «быть знаменитым некрасиво».

83

Число перестановок фразы, состоящей из трех различных слов, равно P3 = 3! = 1 2 3 = 6. Запишем эти шесть вариантов:

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

Количество комбинаций быстро растет с увеличением числа составляющих фразу слов. Например, фраза из четырех слов «быть очень знаменитым некрасиво» дает 24 комбинации перестановок слов, фраза из пяти слов «быть очень знаменитым совсем некрасиво» порождает 120 комбинаций перестановок этих слов.

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

«Квартет».

Напомним, что в ходе этого творческого поиска Îñ¸ë внес предложение: «Ìû, верно, уж поладим, коль рядом сядем». Все равно это им не помогло, хотя в ряд можно сесть по-разному. Различных способов «усесться чинно в ряд» по формуле для числа перестановок имеется P4 = 4! = = 1 2 3 4 = 24. Новые варианты, безусловно, могли бы украсить популяр-

ную басню Крылова.

Теперь представим, что «музыканты» сели не в ряд, а по кругу. В этом случае можно рассуждать следующим образом. Пусть, например, Îñ¸ë садится куда угодно, понятно почему. Если считать одинаковыми остальные расположения «музыкантов» при вращении их по кругу, то тогда число оставшихся пересадок относительно Îñëà равно P3 = 3! = 6. Поэтому число различных способов рассадки наших «музыкантов» по кругу равно шести,

íî что это добавит к звучанию квартета?

Замечание. Если рассматривать перестановки n предметов, расположенных не в ряд, а по кругу, и считать одинаковыми расположения, пе-

реходящие друг в друга при вращении, то число различных перестановок равно Pn–1 = (n – 1)!.

Рассмотрим, например, сколькими способами 7 девушек могут организовать хоровод? Для решения задачи отметим одну из девушек, скажем самую красивую. Теперь надо указать, где будут располагаться остальные девушки: кто будет первой по кругу от самой красивой, кто второй, третьей, …, шестой. Задача свелась к пересчету способов расположения шести оставшихся девушек в последовательность, по существу речь идет обо всех перестановках из n – 1 элемента, где n = 7. Число таких перестановок равно (n – 1)! = 6! = 1 2 3 4 5 6 = 720.

84

Перестановки букв некоторого слова называют анаграммами.

Открытые еще в III веке до нашей эры греческим грамматиком и поэтом Ликофроном анаграммы до сих пор привлекают внимание языковедов, поэтов и любителей словесности. Мастера словесных игр помимо эрудиции и большого запаса слов знают много секретов, связанных с комбинаторными навыками, один из которых — анаграммы. Часто требуется среди всех перестановок выбрать те, которые обладают определенным свойством. Например, среди анаграмм слова КОРТ, которых всего P4 = 4! = 24, только одна, не считая самого слова КОРТ, имеет смысл в русском языке — КРОТ.

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

АВТОР – В[Ф]ТОРА – ОТВАР – РВОТА – ТАВРО – ТОВАР.

Заметим, что тут всего 6 из 120 анаграмм для слова АВТОР. Любопытно, что одно из слов с наибольшим числом различных букв, найденное электронной вычислительной машиной, РАЗГИЛЬДЯЙСТВО содержит четырнадцать букв.

Известна старинная головоломка, в которой надо найти набор слов,

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

ÁÛÊ, ÂßÇ, ÃÍÎÉ, ÄÈ×Ü, ÏËÞÙ, ÑÚÅÌ, ÖÅÕ, ØÓÐÔ, ÝÒÀÆ.

Неизвестно существует ли набор, состоящий из меньшего числа слов. Åñëè ïîä «словом-головоломкой» понимать любую комбинацию из 33 не повторяющихся букв, то тогда теоретически возможно 33! вариантов решения этой головоломки. Эту старинную головоломку можно усложнить, если потребовать, чтобы слова образовывали осмысленную фразу.

Заметим, что в определенном смысле число 10!, которое примерно равно 3,6 миллиона, по мнению автора трехтомного труда «Искусство программирования для ЭВМ» американского математика Дональда Кнута, является «границей между тем, что можно сосчитать на компьютере, и тем, что нельзя». Если алгоритм требует перебора более чем 10! вариантов, то такой счет может занять слишком много машинного времени, чтобы быть практически осуществимым. Поэтому важно уметь находить такие соображения, которые позволяют существенно сократить перебор вариантов.

Иногда бывает нужно из n имеющихся различных объектов отобрать произвольные m øòóê (m n) и расположить их в некотором порядке. Сколько существует упорядоченных расположений при заданных числах n и m?

85

Например, пусть даны четыре буквы А, Б, В, Г. Требуется выделить из них две буквы и эти две буквы расположить в определенном порядке. Таких способов 12. Действительно, первую букву можно выбрать четырьмя способами, а вторую придется выбирать из оставшихся трех, следовательно, в силу комбинаторного принципа умножения всего получается 4 3 = 12 способов. Запишем их в виде упорядоченных множеств:

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

Пример. Рассмотрим, сколькими способами можно разложить m пронумерованных шаров в n пронумерованных корзин (m n), так, чтобы в

каждой корзине оказалось не больше одного шара.

Решим сначала частный случай этой задачи для n = 4 è m = 2. Первый шар мы можем положить в любую из четырех имеющихся корзин, после чего второй шар может быть размещен в любой из оставшихся трех кор-

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

риантов.

Для большей наглядности мы обозначили корзины по порядку буквами А, Б, В, Г, а шары — числами 1 и 2. В вершины графа-дерева (рис. 2.2) поместили обозначения корзин соответствующими буквами А, Б, В и Г.

Это рассуждение можно распространить на случай произвольных n è m следующим образом:

первый шар может быть положен в любую из n корзин;

второй шар может быть положен в любую из оставшихся n – 1 корзин;

……………………………………………………………………………..

m-é øàð может быть положен в любую из оставшихся n – (m – 1) корзин.

Таким образом, всего получается n(n – 1) … (n – (m – 1)) способов.

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

зывают размещениями.

Напомним, что нас интересует следующий вопрос: сколько упорядо- ченных множеств по m элементов в каждом можно получить из заданно-

86