Элементы комбинаторного анализа

Языковеду постоянно приходится решать задачи, в которых рассматриваются комбинации и расположения элементов, принадлежащих определенному лингвистическому множеству. Так, например, синтаксисту важно знать, сколько позиционных вариантов может давать в устно-разговорной речи предложение сегодня идет дождь. Фонетисту и специалисту в области кодирования текста нужно знать, сколько двухбуквенных, трехбуквенных и т.д. комбинаций может дать русский алфавит. Иногда при этом нужно выяснить, какая часть этих комбинаций образует слова и их формы, использующиеся в современном русском (английском или французском) языке. Задачи, в которых требуется ответить на вопрос «сколько?» или «сколькими способами?», называются комбинаторными, а раздел математики, занимающийся решением подобных задач, именуется комбинаторикой.

Комбинаторика (комбинаторный анализ, комбинаторная математика) – раздел математики, посвящённый решению задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами.

Например, путем перебора нетрудно установить, что предложение сегодня идет дождь имеет в русской разговорной речи 6 вариантов: сегодня идет дождь; сегодня дождь идет; дождь сегодня идет; дождь идет сегодня; идет сегодня дождь; идет дождь сегодня. Однако число комбинаций быстро растет с увеличением числа составляющих их элементов. Так, четыре слова (увы, сегодня, дождь, идет) дают 24, пять слов – 120, шесть – 720 позиционных вариантов и т. д. Не все из этих вариантов допустимы с точки зрения норм современного литературного языка. Определить допустимые варианты путем простого перебора оказывается зачастую невозможным. Поэтому, сталкиваясь с такими комбинаторными задачами, прибегают к типовым схемам решения, учитывающим лингвистические или какие-либо другие ограничения.

Принцип умножения. Пусть необходимо выполнить одно за другим какие-то k действий. Если первое действие можно выполнить n₁ способами, после чего второе действие можно выполнить n₂ способами, после чего третье действие можно выполнить n₃ способами, и так далее до k -го действия, которое можно выполнить n_k. способами, то все k. действий вместе могут быть выполнены n₁ * n₂ * n₃ * ... * n_k способами.

Принцип сложения. Если два действия взаимно исключают одно другое, причем одно из них можно выполнить m способами, а другое — n способами, то какое-либо одно из них можно выполнить m+n способами.

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

1. Размещения. Предположим, что имеется алфавит, включающий п элементов. Из этих элементов составляются m -членные комбинации (соединения), причем каждый из п элементов может входить в соединение не более одного раза.

Такой тип комбинаций называется размещением. Число размещений из п элементов по т определяется по формуле:

 

Пример. Из 32 букв русского алфавита можно составить

 

двухбуквенные комбинации, не содержащие повторений букв. По данным четырехтомного «Словаря русского языка» (М., 1957–1961), из этих сочетаний только 114 выступает в качестве самостоятельных слов (имена собственные, сокращения, архаизмы и диалектные слова при этом не учитываются).

2. Размещения с повторениями. Снова возьмем алфавит из п элементов и будем составлять m -членные соединения, допуская повторения каждого элемента от 0 до m раз. Тогда общее число соединений, называемых размещениями с повторениями, находится по формуле

Пример. Из 30 букв русского алфавита (исключая ь и ъ ) можно составить 30² = 900 двухбуквенных серий (например, для денежных знаков) и 30³ = 27 000 трехбуквенных серий.

3. Перестановки. Пусть размещения из п разных элементов взяты по п элементов, т.е. каждое размещение содержит все п элементов алфавита и отличается от других лишь порядком этих элементов. Такие размещения называются перестановками. Для нахождения числа перестановок используют формулу P_n = n!

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

Pⁿ_{n1 , n2 ,... nk} = , где п — общее количество элементов, входящих в перестановку, a n₁, n₂,, n_k — количество одинаковых элементов в первой, второй,..., k-й группах.

Пример. Определим число перестановок с повторениями, которое можно получить из букв, составляющих словоформу математика. Всего в перестановках участвует десять букв, т. е. n = 10; буква м повторяется два раза, поэтому если бы все остальные буквы были различными, то искомое число перестановок, было бы равно P₂¹⁰ = 10! / 2!. На самом деле, кроме двух одинаковых м в нашем слове имеются три а и два т. Поэтому общее число перестановок, полученных из букв, входящих в словоформу математика, равно

P¹⁰_2,2,3⁼

5. Сочетания. В размещениях из n элементов по m соединения отличаются друг от друга либо элементами, либо их порядком, либо и элементами и их порядком. Объединим в отдельные группы такие комбинации, Объединим в отдельные группы такие комбинации, которые содержат т одинаковых элементов и отличаются друг от друга только порядком этих элементов. Нетрудно заметить, что в каждой группе будет ровно Р_т элементов. Группы комбинаций, различающиеся только элементами, называются сочетаниями из п элементов по т. Их число равно

 

6. Сочетания с повторениями. Сочетаниями из п элементов по т с повторениями называются такие соединения, которые включают т из п различающихся между собой элементов при условии, что один и тот же элемент может включаться в комбинацию несколько раз. Два соединения считаются различными, если они отличаются хотя бы одним элементом, и одинаковыми, если они состоят из одних и тех же элементов. Число сочетаний из п элементов по т с повторениями определяется по формуле

ЗАДАЧИ С РЕШЕНИЯМИ

Задача 1. В группе 30 студентов. Необходимо выбрать старосту, заместителя старосты и профорга. Сколько существует способов это сделать?

Решение. Старостой может быть выбран любой из 30 студентов, заместителем - любой из оставшихся 29, а профоргом – любой из оставшихся 28 студентов, т.е. n₁=30, n₂=29, n₃=28. По правилу умножения общее число N способов выбора старосты, его заместителя и профорга равно N=n₁´n₂´n₃=30´29´28=24360.

Задача 2. Два почтальона должны разнести 10 писем по 10 адресам. Сколькими способами они могут распределить работу?

Решение. Первое письмо имеет n₁=2 альтернативы – либо его относит к адресату первый почтальон, либо второй. Для второго письма также есть n₂=2 альтернативы и т.д., т.е. n₁=n₂=…=n₁₀=2. Следовательно, в силу правила умножения общее число способов распределений писем между двумя почтальонами равно

.

Задача 3. В ящике 100 деталей, из них 30 – деталей 1-го сорта, 50 – 2-го, остальные – 3-го. Сколько существует способов извлечения из ящика одной детали 1-го или 2-го сорта?

Решение. Деталь 1-го сорта может быть извлечена n₁=30 способами, 2-го сорта – n₂=50 способами. По правилу суммы существует N=n₁+n₂=30+50=80 способов извлечения одной детали 1-го или 2-го сорта.

Задача 5. Порядок выступления 7 участников конкурса определяется жребием. Сколько различных вариантов жеребьевки при этом возможно?

Решение. Каждый вариант жеребьевки отличается только порядком участников конкурса, т.е. является перестановкой из 7 элементов. Их число равно

Задача 6. В конкурсе по 5 номинациям участвуют 10 кинофильмов. Сколько существует вариантов распределения призов, если по всем номинациям установлены различные премии?

Решение. Каждый из вариантов распределения призов представляет собой комбинацию 5 фильмов из 10, отличающуюся от других комбинаций, как составом, так и их порядком. Так как каждый фильм может получить призы как по одной, так и по нескольким номинациям, то одни и те же фильмы могут повторяться. Поэтому число таких комбинаций равно числу размещений с повторениями из 10 элементов по 5:

Задача 7. В шахматном турнире участвуют 16 человек. Сколько партий должно быть сыграно в турнире, если между любыми двумя участниками должна быть сыграна одна партия?

Решение. Каждая партия играется двумя участниками из 16 и отличается от других только составом пар участников, т.е. представляет собой сочетания из 16 элементов по 2. Их число равно

Задача 8. В условиях задачи 6 определить, сколько существует вариантов распределения призов, если по всем номинациям установлены одинаковые призы?

Решение. Если по каждой номинации установлены одинаковые призы, то порядок фильмов в комбинации 5 призов значения не имеет, и число вариантов представляет собой число сочетаний с повторениями из 10 элементов по 5, определяемое по формуле

Задача 9. Садовник должен в течении трех дней посадить 6 деревьев. Сколькими способами он может распределить по дням работу, если будет сажать не менее одного дерева в день?

Решение. Предположим, что садовник сажает деревья в ряд, и может принимать различные решения относительно того, после какого по счету дерева остановиться в первый день и после какого – во второй. Таким образом, можно представить себе, что деревья разделены двумя перегородками, каждая из которых может стоять на одном из 5 мест (между деревьями). Перегородки должны стоять там по одной, поскольку иначе в какой-то день не будет посажено ни одного дерева. Таким образом, надо выбрать 2 элемента из 5 (без повторений). Следовательно, число способов .

Задача 10. Сколько существует четырехзначных чисел (возможно, начинающихся с нуля), сумма цифр которых равна 5?

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