Изучение основ комбинаторики и теории вероятностей (стр. 5 из 17)
1.4.4. Задачи о смещениях (о беспорядках)
Имеется 5 разных предметов. Сколько можно составить различных комбинаций, в которых ни один предмет не стоит на своем месте? Решим задачу с помощью теоремы о включениях и исключениях:
При решении этой задачи мы использовали частный случай теоремы о включениях и исключения, которая требует определить, что понимается под объектами и что под свойствами этих объектов. Общее число объектов равнялось 5!, так как под объектом мы будем понимать различные расстановки пяти предметов. Под первым свойством понимаем наличие первого предмета на своем месте, под вторым - наличие второго предмета на своем месте и т. д. Всего оказалось 5 свойств.
1.4.5. Задача о караване
Рассмотрим еще одну задачу, в которой решение может быть получено с помощью главной теоремы комбинаторики. 9 верблюдов идут гуськом. Сколько существует комбинаций перестановки верблюдов, при которых ни один верблюд не идет за тем, за кем шел ранее.
Выделим запрещенные пары: (1, 2), (2, 3), (3,4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9). Для решения применим главную теорему комбинаторики. Для этого определим, что есть объект и что есть свойства. Под объектами будем понимать различные расстановки верблюдов. Всего их будет N= 9!. Под свойствами будем понимать наличие определенной пары в перестановке. Таким образом число свойств равно 8. Тогда количество перестановок, не обладающих ни одним из 8 свойств:
В общем случае при п верблюдах имеем
1.4.6.Комбинаторика разбиений
При анализе стратегий различных игр требуется подсчитывать количество комбинаций при раскладе определенных предметов. Наиболее распространенная карточная игра - преферанс. В классическом варианте этой игры карты раскладываются на 3 кучки (по числу играющих) и 2 карты кладутся в "прикуп". Играют 32 картами, т. е. каждый игрок получает по 10 карт.
Определим количество вариантов расклада при игре в преферанс:
Для обоснования полученной формулы расставим все карты подряд и переставим их 32! способами. При каждой перестановке будем выделять первые 10 карт первому игроку, вторую десятку - второму, третью
- третьему, а последние 2 карты будем откладывать в "прикуп". После этого заметим, что перестановка 10 карт в руках каждого игрока не меняет варианта расклада, как и положения 2 карт в прикупе. Поэтому 32! разделим три раза на 10! и еще на 2!
При игре в древнюю китайскую игру НИМ раскладываются п спичек на 3 кучки. Сколько вариантов раскладки этих спичек?
Для определения количества вариантов расклада выпишем подряд п единиц и справа добавим к ним 2 нуля. Переставляя эти объекты всеми возможными способами, мы каждый раз будем получать один из вариантов расклада. Более того, любому варианту расклада можно сопоставить некоторую перестановку из п единиц и двух нулей. Таким образом, получаем:
P(n,2) = (n+2)!/(n!2!).
А теперь определите количество вариантов расклада, при котором в любой кучке есть хотя бы одна (две, три) спички?
В общем случае, если раскладываются п разных предметов по к ящикам так, чтобы в 1-й ящик (кучку, игроку в руки) попало п1предметов, во второй п2предмета, в к-й- пкпредметов, при этом п1+ п2+ ...+ пк = п, то число вариантов расклада
1.4.7. Количество делителей числа N
Прежде чем перейти к рассмотрению задачи о количестве делителей произвольного числа, решим вспомогательные задачи. Пусть студенту на сдачу выдали 5 одинаковых рублей, которые он положил в два кармана. Сколько существует вариантов расклада 5 рублей по двум карманам? Построим таблицу расклада.
1-й карман 5 р., 4 р., 3 р., 2 р., 1 р., 0 р.
2-й карман 0 р., 1 р., 2 р., 3 р., 4 р., 5 р.
Итого существует 6 вариантов расклада. Если раскладывается п предметов на 2 кучки, то существует п + 1 вариант.
Если раскладываются предметы нескольких типов на 2 кучки (ящики, корзины, множества), то такой расклад выполняется независимо для каждого типа предметов и результаты перемножаются.
Пример. Имеются цветы трех видов: 10 васильков, 15 незабудок, 12 ромашек. Требуется разложить их на 2 букета. Васильки на 2 букета можно разложить 11 способами, незабудки - 16, ромашки - 13 способами. Поскольку расклад каждого вида цветов выполняется независимо, то общее число вариантов расклада будет:
.Обобщим полученный результат. Пусть имеется п1предметов 1-го типа, п2 - 2-го, ... пk — k-го. Требуется разложить эти предметы на 2 кучки.
Тогда полное число вариантов расклада равно
Пусть имеется некоторое число N. Требуется определить количество делителей N.
Решение. Представим N в канонической форме, т. е.
Тогда задача о нахождении числа делителей N сводится к задаче раскладки степеней простых чисел на 2 делителя: т. е. решение будет:
Пример. N= 600 = 233152. Число делителей равно (3+1)(1+1)(2+1) = 24.
При решении комбинаторных задач для нахождения числа благоприятных комбинаций иногда удобнее вычислить число неблагоприятных комбинаций и вычесть их количество из общего числа комбинаций.
Пример 1. Из n различных чисел требуется отобрать к таких, чтобы в выбранное множество не входили sконкретных чисел. Общее число выборов из п по к:
Выберем теперь sконкретных чисел и остальные доберем
способами. Это будет число неблагоприятных комбинаций. Число благоприятных комбинаций определится разностью
Пример 2. Из группы в 15 человек нужно отобрать бригаду, в которую должно входить не менее 5 человек. Сколько имеется вариантов выбора?
Подсчитаем число неблагоприятных комбинаций выбора, т. е. составим варианты бригад из 1, 2, 3, 4 человек. Их количество равно:
А общее количество бригад равно 215 – 1. Разность дает число благоприятных комбинаций.
Пример 3. Комиссия из 7 человек хранит свои материалы в сейфе. Сколько должно быть замков на сейфе и сколько должно быть ключей у каждого члена комиссии, чтобы сейф мог быть открыт, если соберутся вместе не менее 4 членов комиссии, но не мог быть открыт при меньшем числе членов комиссии?
Для решения последней задачи можно использовать так называемые "равновесные" коды. Равновесными кодами длины п веса к называются двоичные последовательности длины п, содержащие ровно к единиц ( и п - к нулей). Число таких кодов определяется выражением: Р(к, п - к). Выпишем, например, все коды длины 5 веса 3:
1) 11100 6) 10011
2) 11010 7) 01110
3) 11001 8) 01101
4) 10110 9) 01011
5) 10101 10) 00111
Легко заметить, что каждый столбец содержит 6 единиц и 4 нуля. Кроме того, если взять любые два столбца и поставить их рядом, то всегда найдется комбинация 00. Если же взять три любых столбца, то комбинации 000 не будет.
Если теперь считать номера строк 1), 2), ..., 10) номерами ключей, а каждый столбец рассматривать как способ выдачи ключей конкретному члену комиссии, то мы получим решение поставленной задачи при 5 членах комиссии и пороговом значении h= 3. Если теперь построить таблицу кодов длины 7 веса 4, мы получим решение исходной задачи.
Полученное решение легко обобщить на произвольное число членов комиссии п и произвольный порог h. Действительно, если построить таблицу равновесных кодов длины п веса к, то число ключей будет равно
, а сейф может быть открыт, если соберется число членов комиссии равное h = п - к + 1.Так, например, пусть п = 4, h = 3, т. е. число членов комиссии равно 4, а сейф должен открываться, если соберется не менее 3 членов комиссии. В общем случае к = п - h+ 1.
Для конкретного примера k = 4 – 3 + 1=2; т. е. нужно построить таблицу равновесных кодов длины 4 веса 2:
1) 1100 4) 0110
2) 1010 5) 0101
3) 1001 6) 0011
Из таблицы видно, что сейф должен иметь в этом случае 6 замков, а ключи должны распределяться в соответствии с таблицей равновесных кодов, т. е. первый член комиссии (первый столбец) получает 1, 2 и 3 ключ, второй член комиссии получает 1,4 и 5 ключ, третий член комиссии получает 2,4 и 6 ключ и четвертый член комиссии получает 3, 5 и 6 ключ.
1.4.8. Раскладка предметов в несколько ящиков
Рассмотрим следующую задачу. Трое мальчиков собрали 40 яблок. Сколько имеется способов раздела яблок между ними?
Напишем 40 единиц и 2 нуля, выполняющих как и ранее функции разделителя, и затем начнем их переставлять всеми возможными способами. Каждой перестановке будет соответствовать некоторый способ раздела 40 яблок на 3 кучки. Каждому способу раздела будет соответствовать некоторый код, содержащий 40 единиц и 2 нуля. Поэтому количество способов раздела:
Р(40,2) = 42!/(2!40!) = 861.