Изучение основ комбинаторики и теории вероятностей (стр. 6 из 17)

Если мы раскладываем п₁предметов 1-го типа, п₂предметов второго, ..., п_кпредметов к-го типа на sкучек, тогда

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

1.4.9. Задача: Флаги на мачтах

Имеется п флагов и к мачт. Сколько разных сообщений можно передать, развешивая флаги на мачтах? В этой задаче важным является не только количество флагов, вывешенных на каждой мачте, но и их порядок.

Сначала будем считать, что все флаги одинаковые. Тогда:

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

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

1.4.10. Задача: Покупка билетов

Перед кассой по продаже билетов стоит очередь из п владельцев рублей и к владельцев полтинников. Билет стоит полтинник. В каком количестве комбинаций очередь пройдет без задержки, если владелец полтинника, подойдя к кассе, получает билет, а владелец рубля - билет и полтинник на сдачу. В кассе предварительно нет полтинников. Ясно, что задача имеет смысл, если п < к.

Возьмем комбинацию, при которой очередь застрянет и запишем ее следующим образом:

(s - рублей иs- полтинников)Р........

Очередь застрянет на рубле, при этом до этого рубля в очереди должно быть одинаковое количество владельцев рублей и полтинников. Добавим спереди полтинник (их станет к + 1) и проинвертируем всю комбинацию (заменим рубли на полтинники, а полтинники на рубли) до рубля, на котором очередь застряла (включая и его). Мы придем к комбинации, содержащей п рублей и к + 1 полтинник, начинающейся с рубля. Можно взять п рублей и к + 1 полтинник (теперь всегда число полтинников строго больше числа рублей) и начать комбинацию с рубля. Обратным преобразованием придем к комбинации, при которой очередь обязательно застрянет.

Таким образом, количество комбинаций, при которых очередь застрянет равно Р(п - 1, к + 1), а общее число комбинаций равно Р(п, к); т. е., число благоприятных комбинаций, при которых очередь пройдет без задержки, будет равно

Р(п, к) – Р(п - 1, к + 1).

Например, при п = 4 и к = 5 число благоприятных комбинаций равно

Р(4, 5) -Р(3, 4) = 9!/(4!5!) - 7!/(3!4!) = 126 - 35 = 91.

1.4.11. Рекуррентные соотношения в комбинаторике

1. Задача о наклейке марок.

Имеются марки достоинством в 4, 6, 10 копеек. На конверт нужно наклеить марки так, чтобы сумма составляла 18 копеек. Сколькими способами можно это сделать?

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

F(N) = F(N- 4) + F(N- 6) + F(N- 10),

где под F(N) понимается количество вариантов наклейки марок общей стоимостью N. Подсчитаем значения F(N) для некоторых начальных N.

F(N) = 0 при N<0. F(0) =1. F(1) = F(2) = F(3) = 0. F(4) = 1. F(5) = 0. F(6) = 1.F(7) = 0. F(8) = 1. F(9) = 0. F(10) = 3. Тогда для N= 18 получаем: F(18) = F(14) + F(12) + F(8) = F(10)+ F(8) + F(4) + F(8) + F(6) + F ( 2) + F(8) = 3 + 1 + 1 + 1 + 1 + 1 = 8.

2. Задача об уплате долга.

В кошельке имеются монеты достоинством в 1, 2, 3, 5, 10, 15, 20, 50 копеек (по одной штуке). Требуется уплатить долг в 73 копейки. Сколько существует вариантов выплаты долга?

Запишем рекуррентное соотношение в общем случае, когда монеты имеют достоинства в к₁ к₂, ... и к_ткопеек и требуется набрать сумму в N копеек:

F(k₁k₂, ...,k_m;N) = F(k₁, k₂, ..., k_т-1;N-k_m) + F(k₁, k₂, ..., к_т-1;N).

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

F(l, 2, 3, 5, 10,15, 20, 50; 73) = F(l, 2, 3, 5,10, 15,20; 73)+F(1,2, 3,5,10,15, 20; 23).

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

F(l, 2,3,5,10,15,20; 23) = F(l, 2,3,5,10,15; 3) + F(l, 2,3,5,10,15; 23)

В первом члене правой части монеты достоинством в 5, 10 и 15 копеек можно не учитывать, так как достоинство каждой из этих монет больше набираемой суммы, т. е. можно правую часть переписать так:

F(l,2,3;3) + F(l,2,3,5,10,15;23) =

=F(1,2; 0) + F(l,2;3 )+ F(l,2, 3, 5,10; 8) +F(1,2, 3, 5,10; 23) = 1+F(1; 1) + F(1; 3)+F(l, 2, 3, 5; 8) + F(l, 2, 3, 5, 10; 23).

Очевидно, что F(l, 2; 0) = 1; F(l, 2; 3) = F(l;l) = 1; F(l; 3) = 0; F(l, 2, 3, 5, 10; 23) = 0. Поэтому правая часть перепишется в виде: 1 + 1 + 0 + F(l, 2,3,5; 8) + 0 = 2 + F(l, 2, 3; 3) + F(l, 2, 3; 8) = 2 + 2 + 0 = = 4. Таким образом, задача имеет 4 различных решения.

Подчеркнем еще раз, что в этой задаче порядок монет не важен.

4. Задача о размене гривенника (10 копеек).

Рассмотрим задачу, в которой сняты ограничения, как на порядок предметов, так и на их количество: размен гривенника монетами достоинством в 1, 2, 3, 5 копеек. Сколько существует способов разменять гривенник?

Для этого случая рекуррентное соотношение имеет вид

S(l, 2, 3, 5; 10) = S(l, 2, 3; 10) + S(l, 2, 3; 5) + S(l, 2, 3; 0).

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

1.5. Связь комбинаторики с другими разделами математики

1.5.1. Теория групп

Рассмотрим группу вращений правильного n-угольника. Порождающим элементом этой группы является перестановка:

все остальные элементы группы могут быть получены возведением последовательно в степени 2, 3, ... п этой перестановки. При этом hⁿ=h⁰. Количество таких перестановок (а, следовательно, и число элементов группы) равно п.

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

1.5.2. Теория вероятностей

Для оценки вероятности появления какого-либо дискретного события широко применяются комбинаторные методы. Приведем некоторые примеры.

а) Игрок в преферанс хочет рискнуть: объявить и сыграть "мизер". Для надежной игры ему требуется, чтобы в прикупе оказалась одна из двух семерок, например бубновая или трефовая. Он хочет оценить вероятность такого события. Вероятность события можно определить,разделив количество благоприятных вариантов на общее число возможных вариантов. Подсчитаем количество вариантов, в которых одна из указанных семерок или сразу обе окажутся в прикупе. Положим бубновую семерку в прикуп, а остальные 21 карты распределим так: по 10 карт двум игрокам и одну в прикуп. Количество комбинаций будет равно: 21!/(10! 10!). Такое же количество комбинаций будет и в случае, когда в прикуп попадет трефовая семерка. Если мы сложим число вариантов в этих 2 случаях, то дважды учтем расклады, при которых обе семерки и бубновая, и трефовая попадут в прикуп, поэтому должны еще вычесть число этих вариантов. Окончательно получим число благоприятных комбинаций: 2(21!/(10! 10!) - 20!/(10! 10!) = 41·20!/(10! 10!). Подсчитаем теперь общее число вариантов (учитываем, что 10 карт находятся у игрока, который хочет сыграть мизер). Общее число вариантов равно: 22!/(10!10!2!). Вероятность благоприятного события: Р = 0,177. Рискнуть можно, но шансов на успех мало.