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

Справочный материал

 

· Правило суммы: если объект первого рода можно выбрать n ₁ способами, а объект второго рода n ₂ способами, то выбор «один объект либо первого, либо второго рода» можно осуществить N = n ₁ + n ₂ способами. Если дополнительно объект третьего рода можно выбрать n ₃ способами, то выбор «один объект либо первого, либо второго, либо третьего рода» можно осуществить N = n ₁ + n ₂ + n ₃ способами и т.д.

 

· Правило произведения: если объект первого рода можно выбрать n ₁ способами, и после каждого такого выбора объект второго рода можно выбрать n ₂ способами, то выбор «один объект первого и один объект второго рода» в указанном порядке можно осуществить N = n ₁∙ n ₂ способами. Если дополнительно после каждого указанного выбора объектов перового и второго рода объект третьего рода можно выбрать n ₃ способами, то выбор «один объект первого рода, один второго рода и один объект третьего рода» в указанном порядке можно осуществить n = n ₁∙ n ₂∙ n ₃ способами и т.д.

· Основной принцип комбинаторики: если имеется k исходных множеств, причем из элементов каждого множества можно составить соответственно n ₁, n ₂, …, n_k комбинаций, то общее число способов, которыми можно составить соответствующую последовательность по одной комбинации из каждого исходного множества, равно N = n ₁ · n ₂ ·…· n_k.

· Размещения из n различных элементов по m без повторяющихся элементов – комбинации, получаемые в результате отбора m различных элементов из данных n (m≤ n) с учетом порядка отбора без возвращения выбранных элементов в исходное множество. Общее число различных размещений без повторяющихся элементов:

N = = n· (n – 1) ·…· (n – m + 1).

· Размещения из n элементов по m с повторениями – комбинации, получаемые в результате отбора m элементов из данных n с учетом порядка отбора, причем выбранный элемент перед выбором следующего возвращается в исходное множество. Общее число различных размещений с повторениями:

N = = n^m.

· Перестановки из n различных элементов без повторяющихся элементов – упорядоченные комбинации, содержащие все n элементов исходного множества. Общее число различных перестановок без повторяющихся элементов:

N = P_n = n!,

где n! – факториал натурального числа n, что означает произведение последовательных натуральных чисел, от 1 до n. Например, 5! = 1· 2· 3· 4· 5 = 120. По определению 0! = 1.

 

· Перестановки с повторениями – упорядоченные комбинации, содержащие по n элементов исходного множества, среди которых n ₁ неотличимых элементов 1-го рода, n ₂ – второго рода, … n_k – k -го рода, причем k ≤ n и n ₁ + n ₂ + … + n_k = n. Общее число различных перестановок с повторениями:

.

· Сочетания из n различных элементов по m без повторяющихся элементов – комбинации, получаемые в результате отбора m различных элементов из данных n (m≤ n) без учета порядка отбора и без возвращения выбранных элементов в исходное множество. Общее число различных сочетаний без повторяющихся элементов:

.

· Сочетания из n элементов по m с повторениями – комбинации, получаемые в результате отбора m элементов из данных n без учета порядка отбора, причем выбранный элемент перед выбором следующего возвращается в исходное множество.Общее число различных сочетаний с повторениями:

N = .

· Метод шифра – метод расчета числа сочетаний с повторениями N = на основе сведения задачи к перестановкам с повторяющимися элементами, представляющими «единицы» и «нули». Таким образом, метод шифра используется в случае, когда ставится задача рассчитать число различных комбинаций, которые могут возникнуть при отборе m объектов из данных n с возможными повторами отбираемых объектов, при этом порядок отбора не сказывается на результате этого отбора. Метод заключается в составлении последовательного ряда «ячеек» произвольной вместимости, количество которых n равно числу отличительных признаков отбираемых объектов. По «ячейкам» распределяются m отбираемых объектов, что фиксируется числом «единиц» в соответствующих «ячейках». Если между каждой парой «ячеек» поставить «нуль», то каждый способ отбора (каждый вариант распределения «единиц») будет представлять собой шифр-код, по которому всегда можно идентифицировать разновидность результата отбора. Поскольку в каждом шифр-коде число «нулей» составит (n – 1), а число единиц равно m, то число возможных различных шифр-кодов будет определяться числом перестановок с повторениями:

.

Задачи

1.1. В продаже 3 вида коробок конфет. Сколькими способами можно заказать набор из 5-ти коробок?

 

1.2. На четвертом курсе инженерно-экологического факультета 8 предметов. Сколькими способами можно составить расписание на субботу, если на этот день запланировано 3 пары по различным предметам?

 

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

 

1.4. На велогонке 8 этапов. Сколькими комбинациями велосипедист может быть поощрен майками лидера этапных заездов?

 

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

 

1.6. Найти число комбинаций из возможных различных месяцев рождения у трех человек, если порядок следования месяцев имеет значение.

 

1.7. Стройуправлением получено 6 одинаковых строительных вагончиков, Сколькими способами можно распределить вагончики между 8-ю стройплощадками?

1.8. Лифт в шестиэтажной гостинице отправляется с цокольного этажа вверх с 3-мя пассажирами. Найти число вариантов распределения пассажиров по 5-ти верхним этажам, если на каждом этаже выходит не более одного пассажира.

 

1.9. По шоссе едут автомобили в одном направлении: 4 отечественные марки и 6 иномарок. Сколько возможно вариантов расположения машин вдоль одной полосы на шоссе?

 

1.10. Сколько различных экзаменационных комиссий, состоящих из 7 человек, может быть образовано из 10 преподавателей?

 

1.11. Столовая базы отдыха предлагает комплексный обед из трех блюд с выбором: на первое – одно из 5-ти блюд, на второе – одно их 4-х и на третье – одно из 4-х. Найти число возможных комбинаций заказать обед из трех блюд.

 

1.12. В чемпионате страны по футболу участвуют 18 команд, причем каждые две команды встречаются между собой 2 раза (один раз в 1-ом круге, второй раз во 2-ом круге). Сколько матчей играется в каждом круге и в течение сезона?

 

1.13. Сколько различных пятизначных чисел можно составить из цифр 1, 2, 3?

 

1.14. Два автора должны написать учебник из 6-ти глав, причем первый должен написать 4 главы, а второй 2. Сколькими способами могут быть распределены главы учебника между авторами?

 

1.15. На старте 15 пловцов. Сколько возможно различных комбинаций распределения 1-го, 2-го и 3-го мест между ними, если случаи одновременного финиша исключаются?

 

1.16. На столе 30 экзаменационных билетов. Сколько комбинаций могут составить номера трех первых взятых билетов?

 

1.17. На лыжной дистанции 4 этапа. Сколько возможно комбинаций отметки лыжника номером лидера?

 

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

 

1.19. В группе 30 студентов. Сколькими способами можно выбрать двух из них на студенческую конференцию университета?

 

1.20. Три свидетеля дали несовпадающие данные по форме носа и подбородка преступника. В остальных чертах его лица их показания совпали. Сколько может быть составлено фотороботов по полученной следователем информации?