Сочетание

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

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

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

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

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

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

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

$\sum _{k=0}^{n}{\binom {n}{k}}x^{k}=(1+x)^{n}.$$\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-xy}}.$$\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-xy}}.$

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

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

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

${\binom {n+k-1}{n-1}}={\binom {n+k-1}{k}}=(-1)^{k}{\binom {-n}{k}}={\frac {(n+k-1)!}{k!\cdot (n-1)!}}.$${\binom {n+k-1}{n-1}}={\binom {n+k-1}{k}}=(-1)^{k}{\binom {-n}{k}}={\frac {(n+k-1)!}{k!\cdot (n-1)!}}.$

Доказательство  

Пусть имеется $n$$n$ типов объектов, причём объекты одного типа неотличимы. Пусть имеется неограниченное (или достаточно большое, во всяком случае, не меньше $k$$k$) количество объектов каждого типа. Из этого ассортимента выберем $k$$k$ объектов; в выборке могут встречаться объекты одного типа, порядок выбора не имеет значения. Обозначим через $x_{j}$$x_{j}$ количество выбранных объектов $j$$j$-го типа, $x_{j}\geq 0$$x_{j}\geq 0$, $j=1,2,\dots ,n$$j=1,2,\dots ,n$. Тогда $x_{1}+x_{2}+\dots +x_{n}=k$$x_{1}+x_{2}+\dots +x_{n}=k$. Но число решений этого уравнения легко подсчитывается с помощью «шаров и перегородок»: каждое решение соответствует расстановке в ряд $k$$k$ шаров и $n-1$$n-1$ перегородок так, чтобы между $(j-1)$$(j-1)$-й и $j$$j$-й перегородками находилось ровно $x_{j}$$x_{j}$ шаров. Но таких расстановок в точности ${\tbinom {n+k-1}{k}}$${\tbinom {n+k-1}{k}}$, что и требовалось доказать.■

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

$\sum _{k=0}^{\infty }(-1)^{k}{-n \choose k}x^{k}=(1-x)^{-n}.$$\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}}.$$\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.