Комбинации с повторениями

Пусть опыт состоит в выборе с возвращением k элементов из некоторого множества, состоящего из n элементов, но без последующего упорядочения. Различными исходами такого опыта будут все возможные наборы, отличающиеся только составом. При этом отдельные наборы могут содержать повторяющиеся элементы. Например, при k=4 наборы {1,1,2,1} и {2,1,1,1} неразличимы для данного эксперимента. Получающиеся в результате данного опыта комбинации называются сочетаниями с повторениями, а их общее число определяется формулой

(1.5)

Пример 1.10. В кондитерской имеется 3 вида пирожных. Сколькими способами можно купить 9 пирожных?

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

Пусть выбор k элементов из некоторого множества, состоящего из n элементов, производится с возвращением и с упорядочением их в последовательную цепочку. Различными исходами такого выбора будут всевозможные наборы (вообще говоря, с повторениями) отличающиеся либо составом элементов, либо порядком их следования. Например, множества {1,1,2,1}, {2,1,1,1}, {1,1,3,1} являются различными комбинациями. Получаемые в результате комбинации называются размещениями с повторениями, а их общее число определяется формулой:

(1.6)

Данная формула легко получается из принципа умножения.

Пример 1.11. В лифт восьмиэтажного дома вошли 5 пассажиров. Сколькими способами могут выйти пассажиры на каждом этаже, начиная со второго?

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

При перестановке букв в слове "толпа" получается P₅ = 5! =120 "слов". Если же переставлять буквы в слове "топот", то получится меньше различных "слов", потому что ни перестановка двух букв "т", ни перестановка двух букв "о" не изменяют "слова". Мы имеем здесь дело с перестановками с повторениями.

Число перестановок из n различных элементов с повторениями, которые можно сделать из k₁ элементов первого типа, k₂ элементов второго типа, … , k_n элементов n-го типа, находится по формуле

(1.7)

Пример 1.12. Сколькими способами можно нанизать на нить 4 зеленых, 5 синих и 6 красных бус?

Решение. Речь идет об отыскании числа перестановок с повторениями, которые можно сделать из k₁=4 элементов первого типа (зеленых бус), k₂=5 элементов второго типа (синих бус) и k₃=6 элементов третьего типа (красных бус). По формуле (1.7) получаем

.

1.7. Комбинаторный способ вычисления
вероятностей по классической схеме

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

Пример 1.13. В урне содержатся 3 синих, 5 красных и 2 белых шара. Из нее наудачу извлекаются сразу два шара. Найти вероятность того, что будут вынуты либо два белых шара, либо два разных цветных шара.

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

Теперь найдем число благоприятствующих возможных исходов. Два белых шара можно вынуть m₁=C₂²=1 способом, два разных цветных шара m₂=C₃¹×C₅¹=3×5=15 способами. Тогда общее число благоприятствующих исходов, в соответствии с принципом сложения, равно m = m₁+m₂ = 16. Таким образом,

Пример 1.14. Наудачу взятый телефонный номер состоит из 5 цифр. Какова вероятность, что в нем все цифры разные?

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

Номера, у которых все цифры разные, – это размещения без повторений

Таким образом, искомая вероятность равна