Сочетание

В комбинаторике сочетанием из $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$-й строки треугольника Паскаля.

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

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

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

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

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

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

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

Сочетания с повторениями

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

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

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

При фиксированном $n$ производящей функцией чисел сочетаний с повторениями из $n$ по $k$ является:

$\sum_{k=0}^{\infty} (-1)^k {-n\choose k} x^k = (1-x)^{-n}.$

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

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

См. также

• Комбинаторика
• Перестановка
• Размещение
• Многочлен

Ссылки

• Р. Стенли. Перечислительная комбинаторика. — М.: Мир, 1990.