КОМБИНАТОРНЫЕ ФОРМУЛЫ

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

Задача 1.Обед в университетской столовой состоит из трех блюд. Первых блюд в меню 5, вторых блюд – 4, а третьих – 3. Сколько дней студент может съедать новый обед, если любая комбинация блюд возможна и один обед от другого должен отличаться хотя бы одним блюдом?

Решение. «Закодируем» обед трехзначным числом , где – номер первого блюда ( ), – номер второго блюда ( ), –номер третьего блюда ( ). При любом фиксированном a параметр b может принимать 4 различных значения. Поскольку сам параметр a может принимать 5 различных значений, то имеется 5 ∙ 4 = 20 различных пар ab. С другой стороны, при каждой фиксированной паре ab параметр c может принимать 3 различных значения. Поэтому количество различных троек равно 20 ∙ 3 = 60. Таким образом, число различных обедов равно 60.

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

Обозначим через число способов, которыми можно заполнить строчку , если для выбора элемента существует вариантов Тогда

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

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

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

Ответ: 120 способов.

Решение этой задачи подводит нас к следующему определению перестановки:

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

Число перестановок не зависит от множества, а зависит только от количества его элементов и вычисляется по формуле

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

Часто формулу для числа перестановок приходится употреблять в «усеченном» виде.

Задача 3.Десять участников финала разыгрывают одну золотую, одну серебряную и одну бронзовую медали. Сколькими способами эти награды могут быть распределены между спортсменами?

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

Решение этой задачи подводит нас к определению размещения: размещение – это набор из различных элементов некоторого множества, состоящего из n элементнов, причем два размещения, отличающиеся порядком следования элементов, считаются различными. Стандартным обозначением для числа размещений элементов из является символ . Число размещений вычисляется по формуле

Это выражение можно переписать в виде .

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

Задача 4.Десять участников полуфинала разыгрывают три путевки в финал. Сколько существует вариантов формирования тройки финалистов?

Решение.Ответ предыдущей задачи придется отвергнуть. Действительно, тройки финалистов, которые отличаются только порядком следования участников (например, Иванов, Петров, Сидоров и Петров, Иванов, Сидоров), следует считать одинаковыми. Фактически, ответ предыдущей задачи нужно разделить на число возможных перестановок призеров, равное Таким образом, число вариантов равно

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

Сочетание–это набор изmразличных элементов некоторого -эле-ментного множества, причем два любых сочетания, отличающиеся порядком следования элементов, совпадают. Стандартным обозначением для числа сочетаний mэлементов из n является символ Число сочетаний вычисляется по формуле .

Числа часто называют биномиальными коэффициентами. Это связано с тем, что они выступают в качестве коэффициентов в формуле бинома Ньютона

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

Приведем ряд дополнительных задач по комбинаторике.

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

Решение. Занумеруем адреса цифрами от 1 до 5. Каждый маршрут определяется набором из пяти цифр, например (2, 5, 3, 4, 1). Наборов из 5 цифр, различающихся порядком следования цифр, будет 5! = 120.

Задача 6.Цифры 0, 1, 2, 3 написаны на четырех разноцветных карточках. Сколько различных четырехзначных чисел можно сложить из этих карточек?

Комментарий.. Первая цифра числа не может быть нулем. Карточку можно использовать в числе только один раз.

Решение. Число различных комбинаций из четырех цифр (карточек) равно 4!. Не все эти комбинации отвечают четырехзначным числам, поскольку существует 3! комбинаций, начинающихся с нуля. Поэтому ответ: 4! – 3! = 18.

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

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

Задача 8.Из трех классов спортивной школы нужно составить команду для соревнований, взяв по одномуученику от класса. Сколько различных команд можно составить, если в одном классе учатся 18, в другом 20, в третьем 22 ученика?

Решение.Воспользуемся правилом произведения, число команд равно произведениючисел 18, 20и22, т. е. 7920.

Задача 9.На плоскости задано множество A, состоящее из 8 точек. Три из них выкрашены в красный цвет и лежат на одной прямой, а остальные расположены так, что проходящая через пару точек прямая не содержит других точек множества. Через каждые две точки множества A проведено по прямой линии. Сколько всего прямых линий получилось?

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

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

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

Задача 11.В ящике находится 20 деталей. Известно, что 5 из них являются стандартными. Из этих деталей выбирают 3. Сколько существует таких способов выбора трех деталей, чтобы среди них была по крайней мере одна стандартная?

Решение 1. Множество всех возможных выборов трех деталей из 20содержит элементов, среди них троек содержит тольконестандартные детали. Поэтому ответом задачи будет .

Решение 2. Указанное в условии множество троек можно представить как объединение трех не пересекающихся множеств. Первое состоит из троек стандартных деталей. Их число . Второе – из троек, в которых две детали стандартные, а одна нестандартная, таких троек . Третье множество состоит из троек, содержащих ровно одну стандартную деталь. Таких троек

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

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

Задача 12.Из 7 разноцветных карточек разрезной азбуки составлено слово колокол.Ребенок, не умеющий читать, случайно рассыпал эти карточки. Сколькими способами из этих карточек он сможет снова составить слово колокол?

Решение. На карточках имеется три буквы о, две буквы к, две буквы л. Поэтому, первая буква слова колокол может быть выбрана двумяспособами, вторая – тремяспособами, третья – двумя. При уже выбранных первых трех буквах четвертая буква может быть выбрана еще двумя способами (поскольку одна буква о уже выбрана). Остальные буквы могут быть выбраны только одним способом. Таким образом, ответ равен произведению чисел 3, 2, 2, 2, т. е. 24.

Задача 13.Имеется прямоугольник, разбитый на клетки. По горизонтали он состоит из n клеток, а по вертикали из – m клеток. Можно двигаться только по сторонам клеток либо вправо, либо вверх. Сколько существует различных путей из левого нижнего угла в правый верхний угол?

Решение. Сопоставим ходам вдоль клеток цифры 0 и 1 таким образом, чтобы 0 означал движение вправо, а 1 – движение вверх. Тогда каждому пути соответствует набор из цифр, причем в каждом наборе будет ровно n нулей и m единиц. Сколько таких наборов? Всего в наборе имеется позиций, и среди них следует разместить m единиц (на остальных местах нули). Выбор таких путей можно осуществить способами.