Элементы комбинаторики.

Комбинаторика - это наука, с который каждый встречается в повседневной жизни: сколько способов выбрать 3 дежурных для уборки класса или сколько способов составить слово из данных букв. В целом, комбинаторика позволяет вычислить, сколько различных комбинаций, согласно некоторым условиям, можно составить из заданных объектов (одинаковых или разных).

Комбинаторный принцип умножения если одну часть действия можно выполнить  k способами, а другую - p способами, то все действие можно выполнить  kp  числом способов.

Пример. Пусть требуется составить набор из ручки, карандаша и линейки. Имеется:

5 различных ручек,

7 различных карандашей,

10 различных линеек.

Сколькими способами можно составить требуемый  набор?

            Решение. Действием в данном случае является составление набора из ручки, карандаша и линейки; действие распадается на три этапа (части): выбрать ручку, выбрать линейку и выбрать карандаш. Первую часть действия – выбрать ручку – можно выполнить пятью способами, вторую часть действия – выбрать карандаш – можно выполнить семью способами, третью часть действия – выбрать линейку – можно выполнить десятью способами. Тогда все действие можно выполнить

5*7*10=350

Число способов. Т.е. возможно 350 вариантов такого набора.

Пример. Сколько существует наборов длины n из нулей и единиц?

            Решение. Действием в данном случае является составление набора длины  из нулей и единиц.

Набор будет составлен, если все n позиций (мест) будут заполнены нулями и единицами. Действие распадается на n частей: заполнить первую позицию, вторую и т.д., заполнить n-ю позицию. Первую часть действия – написать первую компоненту - можно двумя способами: можно написать 0, а можно написать 1, написать вторую компоненту тоже можно двумя способами, и так все n мест в наборе: на каждом месте можно написать либо 0 либо 1:

Тогда все действие согласно комбинаторному принципу умножения можно выполнить 2n числом способов:

 

 Комбинаторный принцип сложения. Если два действия взаимно исключают друг друга, и одно из них можно выполнить k способами, а другое - p способами, то оба действия можно выполнить k+p числом способов.

Пример.

Выборкой объема k из множества M={a₁; a₂; …; a_n}  называется всякая последовательность из k элементов множества M.

Если элементы в выборке не повторяются, то выборка называется бесповторной, иначе – выборкой с повторениями.

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

Расположение элементов  выборки в определенном порядке называется упорядочением , при этом выборка называется упорядоченной, в противном случае –неупорядоченной.

 

Задача 1. У мамы 2 яблока и 3 груши. Каждый день в течение 5 дней подряд она выдает по одному фрукту. Сколькими способами это может быть сделано?

Решение. Имеем набор {я, я, г, г, г}. Всего перестановок пятиэлементного множества 5!, но мы не должны учитывать перестановки, в которых объекты одного типа меняются местами несколько раз, поэтому нужно поделить на возможное число таких перестановок: 2! · 3!. Получаем в итоге 5!: (2! · 3!) = (3 · 4 · 5): (2 · 3) = 10.

Задача 2. Предприятие может предоставить работу по одной специальности 4 женщинами, по другой - 6 мужчинам, по третьей - 3 работникам независимо от пола. Сколькими способами можно заполнить вакантные места, если имеются 14 претендентов: 6 женщин и 8 мужчин?

Решение. Имеем 14 претендентов и 13 рабочих мест. Сначала выберем работников на первую специальность, то есть 4 женщин из 6: C4:6 = 6!: (4! · 2!) = 15.

Далее независимо аналогичным образом выберем мужчин на вторую специальность: C6 8 = 8!: (6! · 2!) = 28.

Осталось 2 женщины, 2 мужчин и 3 вакантных места, которые, по условию, могут занять любые из четырех оставшихся человек. Это может быть сделано 2 вариантами: 1. 1 женщина и 2 мужчин (выбираем женщину C1 2 = 2 способами) 2. 1 мужчина и 2 женщины (выбираем мужчину C1 2 = 2 способами). В итого получаем 15 · 28(2 + 2) = 1680 способов.

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

1 уровень
В мешке у Деда Мороза лежит 3 машинки, 5 солдатиков и 7 коробок конфет. Сколькими способами Дед Мороз может вручить один подарок Пете?
           2 уровень
Сколько существует трёхзначных чисел, в которых есть цифра 1?
           3 уровень
Сколькими способами чёрную и белую ладьи можно поставить на шахматную доску 8×8 так, чтобы они не били друг друга?