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

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

Определение. Размещением из п элементов по k элементов (0 ≤ k ≤ n) называется любое упорядоченное подмножество данного множества, содержащее k элементов.

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

Число размещений из п элементов по k обозначается символом и вычисляется по формуле

(1.1)

где n! = 1 ∙ 2 ∙ 3 ∙...∙ n, причём 1! = 1, 0! = 1.

Замечание. Это произведение k уменьшающихся на 1 целых чисел начиная с п.

Определение. Перестановкой из п элементов н азывается размещение из п элементов по п элементов.

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

Число перестановок из п элементов обозначается символом Р_п и вычисляется по формуле

(1.2)

Определение. Сочетанием из п элементов по k (0 ≤ k ≤ n) называется любое подмножество данного множества, которое содержит k элементов.

Любые два сочетания отличаются друг от друга хотя бы одним элементом (т. е. отличаются только составом элементов). Число сочетаний из п элементов по k обозначается символом и вычисляется по формуле

(1.3)

Для чисел (они называются биномиальными коэффициентами) справедливы следующие тождества:

(правило симметрии),

(правило Паскаля),

; ;