Русская Википедия:Сочетание

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

В комбинаторике сочетанием из <math>n</math> по <math>k</math> называется набор из <math>k</math> элементов, выбранных из <math>n</math>-элементного множества, в котором не учитывается порядок элементов.

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

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

Файл:Combinations without repetition; 5 choose 3.svg

3х элементные подмножества 5 элементного множества

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

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

<math>{n\choose k} = C_n^k = \frac{n!}{k!\left(n-k\right)!}.</math>

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

<math>\sum_{k=0}^n \binom{n}{k} x^k = (1+x)^n.</math>

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

<math>\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}.</math>

Шаблон:Anchor Сочетания с повторениями

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

Число сочетаний с повторениями из <math>n</math> по <math>k</math> равно:

<math>\overline{C^k_n}=C^k_{(n)}=\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)!}.</math>

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

<math>\sum_{k=0}^{\infty}\left[(-1)^k {-n\choose k}\right] x^k = (1-x)^{-n}.</math>

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

<math>\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}.</math>

См. также

• Комбинаторика
• Многочлен
• Мультиномиальный коэффициент
• Перестановка
• Размещение

Ссылки

• Шаблон:Книга