Комбинаторика


Правила сложения и умножения в комбинаторике

Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В – n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m способами.

Пример 1.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?

Решение

Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.

По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.


Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n1 способами, второе действие n2 способами, третье – n3 способами и так до k-го действия, которое можно выполнить nk способами, то все k действий вместе могут быть выполнены:

способами.

Пример 2.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить двух дежурных?

Решение

Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.

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

По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.



Пусть имеется n различных объектов.

Будем выбирать из них mm объектов и переставлять всеми возможными способами между собой (то есть меняется и состав выбранных объектов, и их порядок). Получившиеся комбинации называются размещениями из n объектов по m, а их число равно

A=n!(n−m)!=n⋅(n−1)⋅...⋅(n−m+1)Anm=n!(n−m)!=n⋅(n−1)⋅...⋅(n−m+1)

Пусть имеется n различных объектов.

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

P=n!=1⋅2⋅3⋅...⋅(n−1)⋅n

Символ n! называется факториалом и обозначает произведение всех целых чисел от 11 до nn. По определению, считают, что 0!=1,1!=1.

Пример всех перестановок из n=3 объектов (различных фигур) - на картинке справа. Согласно формуле, их должно быть ровно P3=3!=1⋅2⋅3=6, так и получается.

С ростом числа объектов количество перестановок очень быстро растет и изображать их наглядно становится затруднительно. Например, число перестановок из 10 предметов - уже 3628800(больше 3 миллионов!).

Пусть имеется n различных объектов.

Будем выбирать из них m объектов все возможными способами (то есть меняется состав выбранных объектов, но порядок не важен). Получившиеся комбинации называются сочетаниями из n объектов по m, а их число равно

C=n!/((n−m)!⋅m!)

Пример всех сочетаний из n=3 объектов (различных фигур) по m=2. Согласно формуле, их должно быть ровно C=3!/((3−2)!⋅2!)=3.


Задачи для самопроверки

Задача 1: У одного мальчика имеется 10 марок для обмена, а у другого – 8. Сколькими способами они могут обменять 2 марки одного на 2 марки другого?

Задача 2: Из 2 математиков и 10 экономистов надо составить комиссию из 10 человек. Сколько есть способов сделать это при условии, что в комиссии должен участвовать хотя бы 1 математик?

Задача 3: План города имеет вид прямоугольника 5*10. Его улицы идут строго параллельно сторонам. На каждом перекрестке водитель имеет право ехать либо вправо, либо вверх. Сколько существует различных маршрутов добраться из нижнего левого угла в правый верхний?

Задача 4:. Сколько существует способов рассадить за круглый стол 5 юношей и 5 девушек так, чтобы они чередовались?

Задача 5: Дано слово «логарифм». Сколько существует способов поменять местами буквы в этом слове так, чтобы в полученном буквосочетании согласные были упорядочены по алфавиту слева направо?

Ответы:

  1. 45
  2. 65
  3. 15!/(10!*5!)
  4. 2*(5!)^2
  5. 336