Сочетание

В комбинаторике сочетанием из $n$ по $k$ называется набор из $k$ элементов, выбранных из $n$ -элементного множества, в котором не учитывается порядок элементов.

Соответственно, сочетания, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми — этим сочетания отличаются от размещений. Так, например, 3-элементные сочетания 2 и 3 ((нестрогие) подмножества, для которых $k = 3$ ) из 6-элементного множества 1 ( $n = 6$ ) являются одинаковыми (в то время как размещения были бы разными) и состоят из одних и тех же элементов 1.

В общем случае число всех возможных $k$ -элементных подмножеств $n$ -элементного множества стоит на пересечении $k$ -й диагонали и $n$ -й строки треугольника Паскаля.^[1]

Число сочетаний

Шаблон:Main

Число сочетаний из $n$ по $k$ равно биномиальному коэффициенту

(\binom{n}{k}) = C_{n}^{k} = \frac{n!}{k! (n - k)!} .

При фиксированном $n$ производящей функцией последовательности чисел сочетаний $(\binom{n}{0})$ , $(\binom{n}{1})$ , $(\binom{n}{2})$ , … является

\sum_{k = 0}^{n} (\binom{n}{k}) x^{k} = (1 + x)^{n} .

Двумерной производящей функцией чисел сочетаний является

\sum_{n = 0}^{\infty} \sum_{k = 0}^{n} (\binom{n}{k}) x^{k} y^{n} = \sum_{n = 0}^{\infty} (1 + x)^{n} y^{n} = \frac{1}{1 - y - x y} .

Шаблон:Anchor Сочетания с повторениями

Сочетанием с повторениями из $n$ по $k$ называется такой $k$ -элементный набор из $n$ -элементного множества, в котором каждый элемент может участвовать несколько раз, но в котором порядок не учитывается (мультимножество). В частности, число монотонных неубывающих функций из множества ${1, 2, \dots, k}$ в множество ${1, 2, \dots, n}$ равно числу сочетаний с повторениями из $n$ по $k$ .