16. Решение комбинаторных задач.

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

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

Рис. 7

1. Из города А в город В ведут пять дорог, а из города В в город С — три дороги. Сколько путей, проходящих через В, ведут из

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

Решение задачи может быть более наглядным, если составить схему, изображенную на рисунке 7. Здесь римские цифры — номера путей из а арабские — номера путей из

2. Сколькими способами можно выбрать гласную и согласную буквы из слова «полка»?

В этом слове две гласные буквы и три согласные. По правилу произведения выбор может быть сделан способами.

3. Имеется 6 пар перчаток различных размеров. Сколькими способами можно выбрать из них одну перчатку на левую руку и одну перчатку на правую руку таку чтобы эти перчатки были различных размеров?

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

Другой способ решения этой задачи основан на формуле для размещений без повторений. Каждый выбор можно задать парой различных чисел где Число таких пар равно

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

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

5. Сколькими способами можно составить четырехцветный флаг из горизонтальных полос, имея четыре различных цвета?

В этом случае различные флаги отличаются друг от друга лишь порядком цветов. Их число равно числу перестановок из четырех элементов,

6. Из колоды, содержащей 52 карты, вынули 10 карт. Сколькими различными способами это можно сделать? В скольких случаях среди этих карт окажется хотя бы один туз? В скольких случаях окажется ровно один туз? В скольких случаях — ровно 4 туза?

Каждый выбор карт из колоды есть выбор -множества из -множества. Это может быть сделано

способами.

Найти число способов, когда среди выбранных карт есть хотя бы один туз, на первый взгляд сложнее — надо разбирать случаи, когда есть ровно один туз, ровно два туза, ровно три туза, ровно четыре туза. Но проще найти сначала, в скольких случаях среди выбранных карт нет ни одного туза — во всех остальных случаях будет хотя бы один туз. Но если среди выбранных карт нет ни одного туза, то выбор совершался не из 52, а из 48 карт (всех карт, кроме тузов), а потому число таких выборов равно Следовательно, хотя бы один туз будет в случаях.

Чтобы найти, в скольких случаях будет ровно один туз, разобьем операцию выбора карт на две — сначала выбирают из четырех тузов один туз — это можно сделать способами. А потом из оставшихся 48 карт выберем 9, что можно сделать способами. По правилу произведения получаем, что весь выбор можно сделать способами.

Наконец, выбор, содержащий четыре туза, можно сделать способами — надо взять 4 туза и выбрать еще 6 карт из 48.

7. В некотором государстве не было двух жителей с одинаковым набором зубов. Какова может быть наибольшая численность населения государства (наибольшее число зубов равно 32)?

Каждому жителю государства соответствует подмножество множества состоящего из 32 зубов, показывающее, каков набор зубов у этого жителя. Общее число подмножеств -множества равно 232. Значит, в государстве не может быть больше, чем 232 жителей.

8. Пусть различные простые числа. Сколько делителей имеет число где некоторые натуральные числа (делители 1 и включаются)?

Каждый делитель числа имеет вид где

Значит, показатель может принимать значений. Но тогда по правилу произведения число кортежей (Эх, (а тем самым и число делителей равно

9. Сколькими способами можно расставить белые фигуры

(2 коня, 2 слона у 2 ладьи, ферзя и короля) на первой линии шахматной доски?

В этой задаче надо найти число кортежей длины 8, имеющих заданный состав (2, 2, 2, 1, 1). Число таких кортежей (т. е. перестановок с повторениями) равно:

10. Пятнадцать занумерованных биллиардных шаров разложены по шести лузам. Сколькими способами это можно сделать?

Поставим каждому числу от 1 до 15 в соответствие номер лузы, в которую положен шар, номер шара равен этому числу. Получим кортеж длины 15, составленный из цифр 1, 2, 3, 4, 5, 6 (номеров луз). Число таких кортежей равно 615.

11. Сколькими способами можно расставить на 32 черных полях шахматной доски 12 белых и 12 черных шашек?

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

способов.

12. Сколькими способами можно составить набор из 8 пирожных, если имеется 4 сорта пирожных?

Поскольку в этой задаче порядок пирожных не играет роли, то каждый набор задается кортежем длины 8 из 4 элементов (названий сортов пирожных), причем порядок компонент кортежа не играет роли. Иными словами, нам надо найти число различных составов таких кортежей. А это число равно числу сочетаний с повторениями из 4 элементов по 8, т. е. Значит, существует 165 различных наборов.