2020-06-12
1011Комбинаторика, статистика и теория вероятностей. Элементы комбинаторики
Рассмотрим несколько типичных для комбинаторики задач.
Задача 1. Майор Зимин ежедневно формирует наряд для поддержания общественного порядка в городе. Наряд состоит из двух человек: старшего наряда и дежурного. В расположении майора находится 20 полицейских. На сколько дней подряд майор Зимин составит график?
Решение. Пусть сначала избирается старший наряда. Поскольку каждый полицейский может быть выбран старшим, то, очевидно, есть 20 способов его выбора. Тогда дежурным может стать каждый из оставшихся 19 полицейских. Любой из 20 способов выбора старшего наряда может осуществиться вместе с любыми из 19 способов выбора дежурного. Поэтому всего существует 20 ∙ 19 = 380 способов формирования наряда. Т.о. на 380 дней майор Зимин может составить график.
Задача 2. В отделении сержанта Сбруева проходят службу 4 новобранца: Белкин, Пенкин, Свечкин и Овечкин. В свободное от нарядов время сержант обучает их, как рассчитаться по порядку. По команде «В одну шеренгу становись!» солдаты выстраиваются справа от Сбруева и по команде «По порядку номеров рассчитайсь!» производят расчет: «первый-второй-третий-четвертый-пятый». После этого сержант перестраивает новобранцев по-новому и расчет повторяется. Сколько раз может Сбруев повторить это упражнение, используя только разные способы построения солдат?
|
|
|
Решение. Первого новобранца стоящего в шеренге можно выделить четырьмя способами; второго, очевидно, тремя способами. На третье место будут претендовать только два человека, и, следовательно, есть два способа заполнить третье место. Для четвертого новобранца места уже не остается, и он выступает последним.
Занумеруем новобранцев: 1 – Белкин, 2 – Пенкин, 3 – Свечкин, 4 – Овечкин.
Составим схему.
Каждый способ выбора первого новобранца может быть скомбинирован с шестью случаями выбора остальных, то число способов составляет
4 ∙ 6 = 24.
Задача 3. Сколькими способами можно выбрать из пяти разных книг какие-либо две и подарить их двум полицейским, в день милиции в городе Брюково?
Решение. Обозначим книги буквами A, B, C, D, E, можно выписать все возможные пары книг, а именно: AB, AC, AD, AE, BC, BD, BE, CD, CE, DE. Мы видим, что их число равно десяти.
Факториал
Определение. Произведение всех последовательных натуральных чисел от 1 до n обозначается n!
n! = 1 · 2 · 3 ·... · n.
Используя знак факториала, можно, например, записать
Факториалы растут удивительно быстро.
Точные значения факториалов
Размещения
Определение. Размещениями из n элементов по m называются такие соединения, которые отличаются друг от друга либо самими элементами, либо порядком их следования.
|
|
|
Пример. При расследовании хищения установлено, что у преступника семизначный телефонный номер, в котором ни одна цифра не повторяется и нет нуля. Следователь, полагая, что перебор этих номеров потребует одного-двухчасов, доложил о раскрытии преступления. Прав ли он?
Решение. Число номеров равно числу размещений из 9 элементов по 7, т.е. равно 
По формуле получаем 
номеров.
Даже если на проверку одного номера тратить 1 минуту, то на все уйдет 3024 часа или 126 суток. Таким образом, следователь – не прав.
Сочетания
Определение. Сочетаниями из n элементов по m называются такие соединения, которые отличаются друг от друга хотя бы одним элементом. (Подмножества, отличающиеся друг от друга только порядком следования элементов, не считаются различными.)
Число сочетаний из n элементов по m обозначается символом 
и вычисляется по формуле:
Пример. В штате прокуратуры областного центра имеется 16 следователей. Сколькими способами можно выбрать 2 из них для проверки оперативной информации о готовящемся преступлении?
Решение. Способов столько, сколько существует двухэлементных подмножеств у множества, состоящего из 16 элементов, т.е. их число равно 
, т.е. всего 120 способов выбора следователей.
Перестановки
Определение. Перестановками из n элементов называются такие соединения из n элементов, которые отличаются друг от друга лишь порядком следования элементов.
Пример. Замок сейфа открывается, если введена правильная комбинация. Преступник пытается открыть сейф, набирая код наудачу. Он знает, что код состоит из цифр 1, 2, 3, 4, 5, 6 при условии, что все числа не повторяются и последней является 5. Сколько попыток ему придется сделать.
Решение. Так как число пять должно стоять на последнем месте, то остальные пять цифр могут стоять на оставшихся местах в любом порядке. Следовательно, количество кодов из шестизначных чисел, с пятеркой на конце, равно числу перестановок из пяти элементов, т.е. 
.
Задача. Сколько четырехбуквенных слов можно образовать из букв слова сапфир?
Решение. P4=4! = 1*2*3*4 =24 (неверно)
.
Треугольник Паскаля
Определение: Треугольник Паскаля - это треугольник, составленный из чисел, являющихся коэффициентами в формуле бином Ньютона.
Каждый крайний элемент равен 1, а каждый не крайний элемент равен сумме двух своих верхних соседей.
Треугольник можно продолжать до бесконечности, но на практике чаще составляют таблицу для первых 10 степеней.
Треугольник Паскаля для n от 1 до 10.
| n | k1 | k2 | k3 | k4 | k5 | k6 | k7 | k8 | k9 | k10 | k11 |
| 1 | 1 | 1 | |||||||||
| 2 | 1 | 2 | 1 | ||||||||
| 3 | 1 | 3 | 3 | 1 | |||||||
| 4 | 1 | 4 | 6 | 4 | 1 | ||||||
| 5 | 1 | 5 | 10 | 10 | 5 | 1 | |||||
| 6 | 1 | 6 | 15 | 20 | 15 | 6 | 1 | ||||
| 7 | 1 | 7 | 21 | 35 | 35 | 21 | 7 | 1 | |||
| 8 | 1 | 8 | 28 | 70 | 70 | 56 | 28 | 8 | 1 | ||
| 9 | 1 | 9 | 36 | 126 | 126 | 126 | 84 | 36 | 9 | 1 | |
| 10 | 1 | 10 | 45 | 210 | 210 | 252 | 210 | 120 | 45 | 10 | 1 |
1. Представьте степень двучлена в виде многочлена, используя бином Ньютона и треугольник Паскаля:
а) 
; б) 
.
2. Найти значение выражения 
.
Решение:
1а) 
1б) 
2. 
Задание для самостоятельного выполнения:
Вычислить 
, 
.
Свойство 
.
