Сочетание

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

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

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

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

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

[math]\displaystyle{ {n\choose k} = C_n^k = \frac{n!}{k!\left(n-k\right)!}. }[/math]

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

[math]\displaystyle{ \sum_{k=0}^n \binom{n}{k} x^k = (1+x)^n. }[/math]

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

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

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

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

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

[math]\displaystyle{ \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]\displaystyle{ n }[/math] типов объектов, причём объекты одного типа неотличимы. Пусть имеется неограниченное (или достаточно большое, во всяком случае, не меньше [math]\displaystyle{ k }[/math]) число объектов каждого типа. Из этого ассортимента выберем [math]\displaystyle{ k }[/math] объектов; в выборке могут встречаться объекты одного типа, порядок выбора не имеет значения. Обозначим через [math]\displaystyle{ x_j }[/math] число выбранных объектов [math]\displaystyle{ j }[/math]-го типа, [math]\displaystyle{ x_j\geq 0 }[/math], [math]\displaystyle{ j=1,2,\dots,n }[/math]. Тогда [math]\displaystyle{ x_1+x_2+\dots+x_n=k }[/math]. Но число решений этого уравнения легко подсчитывается с помощью «шаров и перегородок»: каждое решение соответствует расстановке в ряд [math]\displaystyle{ k }[/math] шаров и [math]\displaystyle{ n-1 }[/math] перегородок так, чтобы между [math]\displaystyle{ (j-1) }[/math]-й и [math]\displaystyle{ j }[/math]-й перегородками находилось ровно [math]\displaystyle{ x_j }[/math] шаров. Но таких расстановок в точности [math]\displaystyle{ \tbinom{n+k-1}{k} }[/math], что и требовалось доказать.■

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

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

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

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

См. также

Примечания

↑ Удивительный треугольник великого француза. (неопр.). Дата обращения: 20 апреля 2010. Архивировано 21 апреля 2010 года.

Ссылки

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

[1] Удивительный треугольник великого француза. (неопр.). Дата обращения: 20 апреля 2010. Архивировано 21 апреля 2010 года.

[1]