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

Очень многие комбинаторные задачи решаются применением трех простых правил: равенства, суммы и произведения.
Правило равенства. Если между конечными множествами A и B есть взаимно однозначное соответствие, то .
Правило суммы. Если A и B – конечные множества и , то .
Правило произведения. Для любых конечных множеств A и B имеет место равенство :

Перестановкой элементов множества М называется всякое соединение элементов множества М, в котором обязательно присутствуют все элементы из М и в котором учитывается порядок следования элементов друг за другом.
Например, если n=3, то (1,2,3) и (3,2,1) являются разными перестановками.
При произвольном n количество Pn всевозможных перестановок множества равно

ПРИМЕР: Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не могли бить друг друга?
Количество ладей
Занимаемые места на доске (1 в горизонтали и 1 в вертикали)

Всякое соединение из k элементов множества , в котором учитывается порядок следования элементов друг за другом, называется размещением из n элементов по k.
При n=k – это перестановка.
При n
При n>k количество размещений из n по k равно:
Очевидно, что

ПРИМЕР: В спортивных соревнованиях исходом является определение участников, занявших 1, 2, 3 места. Сколько возможно различных исходов, если в соревнованиях участвуют n участников?

Всякое соединение из k элементов множества , где в котором порядок следования элементов друг за другом не учитывается, называется сочетанием из n по k.
Например, при n=4, соединения (3,1,4) и (4,1,3) являются различными размещениями из 4
по 3, но как сочетания они равны.
Количество сочетаний из n по k определяется следующей формулой:

ПРИМЕР: В начале игры в домино каждому играющему выдаётся 7 костей из имеющихся 28. Сколько существует различных комбинаций костей, которые игрок может получить в начале игры?

Размещение с повторениями из n элементов множества M по k - всякая конечная последовательность, состоящая из k членов данного множества M, все k элементов которой не обязательно различны.
Два размещения с повторениями считаются различными, если хотя бы на одном месте они имеют различные элементы множества M.
Возьмем буквы Б, А, Р. Какие размещения из этих букв, взятых по две, можно получить? Сколько таких наборов получиться, если буквы могут повторяться?
Получатся наборы: ББ, БА, БР, АА, АБ, АР, РР, РБ, РА.

Перестановки с повторениями
Число различных перестановок, которые можно построить из n элементов, среди которых находятся n1элементов первого типа, n2 элементов второго типа,…, nk элементов k-го типа равно