Задачи для самостоятельного решения

1. На собрании должны выступить 5 человек: А, Б, В, Г, Д. Сколькими способами можно расположить их в списке ораторов при условии, что Б не должен выступать до того, как выступит А? Если А должен выступить непосредственно перед Б?

2. Сколькими способами можно переставить буквы слова «переcечение» так, чтобы четыре буквы «е» не шли подряд?

3. Сколькими способами можно переставить буквы слова «бином» так, чтобы буква «н» шла непосредственно после «о»?

4. Сколькими способами можно переставить буквы слова «импликация» так, чтобы две буквы «и» не шли подряд?

5. Сколькими способами можно переставить буквы слова «стохастика» так, чтобы никакие две гласные не стояли рядом?

6. На полке находятся т+п различных книг, из которых т в черных переплетах, а n в красных. Сколько существует перестановок этих книг, при которых книги в черных переплетах занимают первые т мест? Во скольких случаях все книги в черных переплетах стоят рядом (не обязательно первыми)?

7. На окружности отмечено п точек. Сколько существует различных многоугольников, вписанных в эту окружность, вершинами которых служат данные точки? Сколько существует различных выпуклых многоугольников, вписанных в эту окружность, вершинами которых служат данные точки?

8. Сколько можно сделать перестановок из п элементов, в которых: а)    данные два элемента а и b не стоят рядом;

б)   данные 3 элемента а, b, с не стоят рядом;

в)    никакие 2 из данных 3 элементов а, b, с не стоят рядом?

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

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

11. Сколькими способами можно переставить буквы слова «функция» таким образом, чтобы между двумя гласными были две согласные буквы?

12. Сколькими способами можно переставить буквы слова «произведение» так, чтобы три буквы «е» не стояли рядом?

Примеры решения некоторых комбинаторных задач

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

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

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

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

Удар! И 15 перенумерованных бильярдных шаров, только что покоившихся на зеленом сукне стола, рассыпались в разные стороны. А затем серия виртуозных ударов и все шары забить в лузы, а на столе остался только биток − шар, которым забивают все остальные. Предположим, что забитые шары остаются лежать в лузах до конца игры, а сетки луз так велики, что могут вместить все 15 шаров. Тогда возникает следующая комбинаторная задача.

Задача. Сколькими способами могут распределиться 15 перенурованных бильярдных шаров в 6 лузах?

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

Если бы число шаров равнялось п, а луз − т, то получилось бы  вариантов размещения шаров по лузам.

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

Задача. Трое ребят собрали с яблони 40 яблок. Сколькими способами они могут их разделить, если все яблоки считаются одинаковыми?

Решение.Задача похожа на предыдущую, но здесь размещаемые предметы одинаковы − нас интересует лишь, сколько яблок получит каждый, но не то, какие именно яблоки ему достанутся, то есть способ раздела задается тройкой чисел (сколько яблок получает первый, второй, третий).

Для решения этой задачи поступим так: добавим к собранным яблокам еще 2 одинаковые груши, а потом переставим всеми возможными способами 40 яблок и 2 груши. По формуле для нахождения числа перестановок с повторениями имеем:

Но каждой перестановке соответствует свой способ раздела яблок. Первому из ребят мы даем все яблоки, начиная от первого и до первой груши, второму − все яблоки, попавшие между первой и второй грушей, а третьему − все яблоки, лежащие после второй груши. Ясно, что при этом различным перестановкам соответствуют разные способы раздела. Таким образом, общее число способов раздела равно 861. При этом может случиться так, что одному (или даже двоим) участникам раздела ничего не достанется. Например, если одна из груш попадает при перестановке в начало, то лишается яблок первый из ребят, а если в конец − то третий. Если же обе груши окажутся рядом, то ничего не получит второй. То есть мы имеем дело с сочетаниями с повторениями  − есть 3 типа предметов (мальчики) и надо делать из них комбинации из 40 элементов (по числу яблок, какое-кому), порядок элементов не учитывается, разные комбинации отличаются количеством предметов хотя бы одного типа (то есть как раз числом яблок, достающимся хотя бы одному мальчику).

Рассмотрим общее утверждение. Число способов размещения п одинаковых предметов по т различным ящикам равно         (*)

Предположим теперь, что для «непустоты» ящиков поставлено условие, чтобы в каждый попало по крайней мере r предметов. В этом случае надо начать с того, что положить в каждый ящик по r предметов. После этого остается n-mr предметов, которые можно уже распределять произвольным образом. А это можно сделать, как следует из формулы (*),  способами.

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

Последний результат можно вывести и иным образом. Расположим данные п предметов в ряд. Тогда между ними будет (n−1) промежутков. Если в любые (m−1) из этих промежутков поставить разделяющие перегородки, то все предметы разделятся на т непустых частей. После этого первая часть кладется в первый ящик, вторая − во второй и т. д. Так как (m−1) перегородку можно поставить в (п−1) промежуток  способами, то это и есть число способов раздела.