Комбинаторика

Задачи по теории вероятностей с решениями

Составитель – доцент А.В.Лебедев, 2010

Комбинаторика

Задача 1. В группе 30 студентов. Необходимо выбрать старосту, заместителя старосты и профорга. Сколько существует способов это сделать?

Решение. Старостой может быть выбран любой из 30 студентов, заместителем - любой из оставшихся 29, а профоргом – любой из оставшихся 28 студентов, т.е. n₁=30, n₂=29, n₃=28. По правилу умножения общее число N способов выбора старосты, его заместителя и профорга равно N=n₁´ n₂´ n₃=30´ 29´ 28=24360.

Задача 2. Два почтальона должны разнести 10 писем по 10 адресам. Сколькими способами они могут распределить работу?

Решение. Первое письмо имеет n₁=2 альтернативы – либо его относит к адресату первый почтальон, либо второй. Для второго письма также есть n₂=2 альтернативы и т.д., т.е. n₁=n₂=…=n₁₀=2. Следовательно, в силу правила умножения общее число способов распределений писем между двумя почтальонами равно

.

Задача 3. В ящике 100 деталей, из них 30 – деталей 1-го сорта, 50 – 2-го, остальные – 3-го. Сколько существует способов извлечения из ящика одной детали 1-го или 2-го сорта?

Решение. Деталь 1-го сорта может быть извлечена n₁=30 способами, 2-го сорта – n₂=50 способами. По правилу суммы существует N=n₁+n₂=30+50=80 способов извлечения одной детали 1-го или 2-го сорта.

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

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

Задача 6. В конкурсе по 5 номинациям участвуют 10 кинофильмов. Сколько существует вариантов распределения призов, если по всем номинациям установлены различные премии?

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

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

Решение. Каждая партия играется двумя участниками из 16 и отличается от других только составом пар участников, т.е. представляет собой сочетания из 16 элементов по 2. Их число равно

Задача 8. В условиях задачи 6 определить, сколько существует вариантов распределения призов, если по всем номинациям установлены одинаковые призы?

Решение. Если по каждой номинации установлены одинаковые призы, то порядок фильмов в комбинации 5 призов значения не имеет, и число вариантов представляет собой число сочетаний с повторениями из 10 элементов по 5, определяемое по формуле

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

Решение. Предположим, что садовник сажает деревья в ряд, и может принимать различные решения относительно того, после какого по счету дерева остановиться в первый день и после какого – во второй. Таким образом, можно представить себе, что деревья разделены двумя перегородками, каждая из которых может стоять на одном из 5 мест (между деревьями). Перегородки должны стоять там по одной, поскольку иначе в какой-то день не будет посажено ни одного дерева. Таким образом, надо выбрать 2 элемента из 5 (без повторений). Следовательно, число способов .

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

Решение. Представим число 5 в виде суммы последовательных единиц, разделенных на группы перегородками (каждая группа в сумме образует очередную цифру числа). Понятно, что таких перегородок понадобится 3. Мест для перегородок имеется 6 (до всех единиц, между ними и после). Каждое место может занимать одна или несколько перегородок (в последнем случае между ними нет единиц, и соответствующая сумма равна нулю). Рассмотрим эти места в качестве элементов множества. Таким образом, надо выбрать 3 элемента из 6 (с повторениями). Следовательно, искомое количество чисел

Задача 11. Сколькими способами можно разбить группу из 25 студентов на три подгруппы А, В и С по 6, 9 и 10 человек соответственно?

Решение. Здесь n=25, k=3, n₁=6, n₂=9, n₃=10. Согласно формуле, число таких разбиений равно

Задача 12. Сколько существует семизначных чисел, состоящих из цифр 4, 5 и 6, в которых цифра 4 повторяется 3 раза, а цифры 5 и 6 – по 2 раза?

Решение. Каждое семизначное число отличается от другого порядком следования цифр, при этом фактически все семь мест в этом числе делятся на три группы: на одни места ставится цифра «4», на другие места – цифра «5», а на третьи места – цифра «6». Таким образом, множество состоит из 7 элементов (n=7), причем n₁=3, n₂=2, n₃=2, и, следовательно, количество таких чисел равно