WikiSort.ru - Не сортированное

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

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

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

В общем случае число, показывающее, сколькими способами можно выбрать ${\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 \{1,2,\dots ,k\}}$ в множество ${\displaystyle \{1,2,\dots ,n\}}$ равно числу сочетаний с повторениями из ${\displaystyle n}$ по ${\displaystyle k}$ .

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

${\displaystyle {\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 }(-1)^{k}{-n \choose k}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}}.}$

См. также

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

Примечания

В Викисловаре есть статья «сочетание»

Ссылки

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