2. Число сочетаний из nэлементов по k.

В комбинаторике сочетанием из $n$ по $k$ называется набор $k$ элементов, выбранных из данного множества, содержащего $n$ различных элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

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

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

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

${n\choose k} = C_n^k = \frac{n!}{k!\left(n-k\right)!}.$

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

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