Основы комбинаторики

Предмет комбинаторики
Комбинаторика – это раздел математики, который изучает задачи выбора и расположения элементов из некоторого множества в соответствии с заданными правилами.
Типичные задачи комбинаторики:
«Сколькими способами можно сделать … ?», «Сколько вариантов существует … ?», «Сколькими способами можно выбрать столько-то объектов?» и т.п.

Предмет комбинаторики
Формулы и принципы комбинаторики используются в теории вероятностей для подсчета вероятности случайных событий и, соответственно, получения законов распределения случайных величин.
Это, в свою очередь, позволяет исследовать закономерности массовых случайных явлений, что является весьма важным для понимания статистических закономерностей.

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

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

Факториал
Факториал – операция произведения всех натуральных чисел от единицы до заданного n включительно:
Например:
По определению:

Свойства факториала
Отношение двух факториалов упрощается следующим образом:

Перестановки без повторений
Число перестановок определяет, сколькими способами можно переставить n элементов множества.
Если элементы множества можно считать различными, то применяется формула подсчета числа перестановок без повторений:

Перестановки с повторениями
Если в рассматриваемом множестве присутствуют одинаковые элементы, причем элементов первого типа n1 штук, элементов второго – n2 штук, третьего – n3 и т.д. до k-го типа элементов, общее число которых равно nk, то применяется формула подсчета числа перестановок с повторениями:

Сочетания без повторений
Число сочетаний определяет, сколькими способами можно выбрать m элементов из множества, состоящего из n элементов.
Если элементы множества можно считать различными, то применяется формула подсчета числа сочетаний без повторений:

Сочетания с повторениями
Если в множестве присутствуют одинаковые элементы, причем число различных типов элементов равно n, и из них требуется выбрать m элементов (причем все m элементов могут быть одного типа), то применяется формула подсчета числа сочетаний с повторениями:

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

Размещения с повторениями
Если каждый из n элементов множества можно выбирать неоднократно, то применяется формула подсчета числа размещений с повторениями: