Основные формулы комбинаторики

Комбинаторика изучает количество комбинаций, которые можно составить из элементов конечного множества.

Перестановками называются комбинации, составленные из одних и тех же различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок из n элементов равно

,                                                          (1)

 где n - натуральное число.

n! называют факториалом числа n   и определяют следующим образом

n! = 1·2·3 ·… n

Например,  3! = 1·2·3 = 6.

Полагают, что  0! = 1.

Пример

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

.

Ответ: 120 способов

 

Размещения– это комбинации, составленные из n различных элементов по k элементов, которые отличаются либо составом элементов, либо их порядком.

Количество размещений из n элементов по k элементов обозначается  и вычисляется по следующей формуле:

                     (2)

 

Пример

Сколько существует способов составить трёхзначное число с различными цифрами из набора {1, 2, 3, 4, 5, 6, 7, 8, 9}?

=9·8·7=504.

Ответ: 504 способа.

 

Сочетания – это комбинации, составленные из n различных элементов по k элементов и отличающиеся хотя бы одним элементом (при этом порядок элементов не является существенным).

Количество сочетаний из n элементов по k элементов обозначается  и вычисляется по следующей формуле:

                                                 (3)

Пример

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

.

Ответ: 45 способов.

Вероятность события

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

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

                                                          (4)

Заметим, что вероятность достоверного события , вероятность невозможного события . Кроме того, из определения вероятности следует, что для любого события  выполняется неравенство:

                                                       (5)

Вероятности сложных событий

Для вычисления вероятностей сложных событий используются следующие теоремы теории вероятностей.

Теорема сложения вероятностей. Если события  и  несовместны, то вероятность их суммы равна сумме их вероятностей:

                                                                                          (6)

Сформулированная теорема справедлива для любого конечного числа слагаемых.

Если же события  и  совместны, то

                                                                                   (7)

Из теоремы сложения вероятностей следует, что если  и  – противоположные события, то

                                         или                                     (8)

Теорема умножения вероятностей. Если события  и  независимы (т.е. вероятность одного из событий не зависит от появления или непоявления другого), то вероятность произведения событий равна произведению их вероятностей:

                                                                                                 (9)

Сформулированная теорема также справедлива для любого конечного числа сомножителей.