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

Представим, что из элементов множества Е={a,b,c,d} мы составляем всевозможные трехэлементные комбинации, но выбрав элемент, мы возвращаем его снова в дано множество и можем выбирать его ещё и ещё раз. Пусть в этом случае нам не важен порядок элементов (как в сочетаниях). При этом мы будем получать комбинации ааb, aba, aac и т.д. Первые две из них мы считаем одинаковыми, так как порядок следования элементов нам в данном случае не важен. Третья же комбинация отлична от первых двух.

Если опыт состоит в выборе с повторениями (с возращением) m элементов из множества E = { а₁,а₂,…а_n } без учёта порядка выбора, то различными исходами такого опыта будут всевозможные m элементные наборы, отличающиеся составом элементов. Получаемые в результате данного опыта комбинации называются сочетаниями с повторениями из n элементов по m, их число обозначается .

Рассмотрим следующую задачу:

В магазине имеются коробки конфет трёх видов. Сколькими способами можно заказать набор, состоящий из пяти коробок?

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

Например, если заказали две коробки конфет первого вида одну – второго вида и две – третьего вида, то это событие зашифруется так 1101011

Если коробок второго и третьего наименования совсем не заказали, то этот факт будет отмечен двумя нулями на конце шифра: 1111100.

Событию «заказано четыре коробки конфет второго вида и одна – третьего» соответствует шифр 0111101.

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

F = {1, 1,1, 1, 1, 0, 0}. В этом множестве единица повторяется 5 раз, а ноль – 2 раза, и, применяя формулу для числа перестановок с повторениями, находим искомое число комбинаций:

 

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

Простые задачи

 

1. Первого сентября на 1 курсе одного из факультетов запланировано по расписанию 3 лекции по разным предметам. Всего на первом курсе изучается 10 предметов. Сколько существует способов составить расписание на 1 сентября?

 

2. На кафедре математики 9 преподавателей. Сколькими способами можно составить расписание консультаций на 9 дней, если каждый преподаватель даёт консультацию ровно один раз?

 

3. На тренировках занимаются 12 баскетболистов. Сколько может быть образовано разных стартовых пятёрок?

 

4. 7 членов профсоюзного комитета должны избрать из своего состава председателя и секретаря. Сколькими способами это можно сделать?

 

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

 

6. В группе студентов 25 человек. Необходимо избрать старосту, его заместителя и профорга. Сколькими способами это можно сделать?

 

7. Сколько существует различных четырёхзначных чисел с неповторяющимися цифрами?

 

8. Сколько существует трехзначных чисел в десятичной системе исчисления?

 

9. Для передачи сигналов на корабле вывешиваются одно под другим три разноцветных полотнища. Сколько разных сигналов можно передать при наличии белого, жёлтого, красного, зелёного, синего и черного полотнищ?

 

11. 25 выпускников школы решили обменяться фотокарточками. Сколько было заказано всего фотокарточек?

 

12. Сколько словарей надо издать, чтобы можно было непосредственно выполнять переводы с любого из пяти языков (русского, английского, французского немецкого и испанского) на любой другой из этих пяти языков?

 

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

 

14. Сколькими способами можно из 15 солдат и 4 офицеров назначить в патруль трёх солдат и одного офицера?

 

15. Для полёта в космос необходимо укомплектовать следующий экипаж: командир корабля, первый его помощник, второй помощник, два бортинженера и врач. Командная тройка может быть отобрана из 25 готовящихся к полёту лётчиков, два бортинженера – из 20 специалистов, врач – из 8 медиков. Сколькими способами можно укомплектовать экипаж?

 

18. У одного человека есть 7 книг по математике, у другого – 9. Сколькими способами они могут обменять книгу одного на книгу другого? Сколько существует способов обмена двух книг одного на две книги другого?

 

19. Пусть в некоторой стране номер автомобиля составляется из двух букв, за которыми следуют две цифры, например: АВ-53. Сколько различных номеров можно составить, если использовать 5 букв и 6 цифр?

 

21. Из 4 инженеров и 9 экономистов составляют комиссию, состоящую из 7 человек. Сколькими способами это можно сделать, если в комиссию должны войти хотя бы 2 инженера?

 

22. Четыре студента сдали экзамен. Известно, что все они получили положительные оценки. Сколько может быть вариантов распределения оценок?

 

23. У Серёжи остались от полного набора штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все свои книги пятизначные номера – составить каталог. Первая книга получила номер 11111, следующая – 11113 и т.д. Сколько различных пятизначных номеров может составить Серёжа?

 

24.Мама купила 2 яблока, 3 груши и 4 апельсина. Она каждый день даёт сыну с собой по одному фрукту. Сколькими способами она может выдать сыну фрукты?

 

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

 

30. Сколько различных четырехзначных чисел можно образовать из цифр 0, 1, 2?

 

31. Для несения почётного караула приглашаются 10 служащих из 6 родов войск. Сколькими способами может быть избран состав караула, если в нём не обязательно должны быть представлены все рода войск?