Сочетание

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

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

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

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

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

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

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

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

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

${\displaystyle \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}}.}$

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

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

Число сочетаний с повторениями из ${\displaystyle n}$ по ${\displaystyle k}$ равно:

${\displaystyle {\overline {C_{n}^{k}}}=C_{(n)}^{k}=\left(\!\!{\binom {n}{k}}\!\!\right)={\binom {n+k-1}{n-1}}={\binom {n+k-1}{k}}=(-1)^{k}{\binom {-n}{k}}={\frac {(n+k-1)!}{k!\cdot (n-1)!}}.}$

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

${\displaystyle \sum _{k=0}^{\infty }\left[(-1)^{k}{-n \choose k}\right]x^{k}=(1-x)^{-n}.}$

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

${\displaystyle \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}}.}$

См. также

Примечания

Ссылки

• Стенли Р.^{<span title="Статья «Стенли, Ричард Питер» в русском разделе отсутствует">ru</span>}_en. Перечислительная комбинаторика. — М.: Мир, 1990.

Эта страница в последний раз была отредактирована 30 июля 2023 в 12:14.