Комбинаторика - основные понятия и формулы. Перестановки, размещения, сочетания

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

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

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

Правило сложения

Если любые две группы  и  не имеют общих элементов, то выбор одного элемента или из , или из , …или из  можно осуществить  способами.

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

Размещения без повторений, когда отобранный элемент перед отбором следующего не возвращается в генеральную совокупность. Такой выбор называется последовательным выбором без возвращения, а его результат – размещением без повторений из  элементов по .

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

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

Размещения с повторениями, когда отобранный элемент перед отбором следующего возвращается в генеральную совокупность. Такой выбор называется последовательным выбором с возвращением, а его результат  - размещением с повторениями из  элементов по .

Общее число различных способов, которыми можно произвести выбор с возвращением  элементов из генеральной совокупности объема , равно

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

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

Число сочетаний из  элементов по  равно:

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

Число сочетаний с повторениями из  элементов по :

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

Число разбиений на  групп, когда в первую попадают  элементов, во вторую -  элементов, в k-ю группу -  элементов, равно: