Сочетание

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

К примеру набор из трёх-элементного созвучия

3n по k=1 {TAR} = 3, состоит из 3ёх звуков , имеет в себе комбинации 6ть групп элементов разложений или отслоений,

по k=2 {TAR + (TA. + .AR) + (T.. + .A. + ..R) } = 6=3⁺!² соответствует трёх-значному треугольнику из шаров , где группы шести элементов с учётом общего количества количеств имеют в себе 10ть единичных элементов

по k=3 {3*1 + 2*2 + 1*3} =10=3⁺!³ трёх-значный тетраэдр.

К примеру набор пяти-элементного созвучия

5n при k=1 {ENTAR} = 5, состоит из 5ти звуков и имеет в себе комбинации 15ть групп элементов разложений или отслоений,

по k=2 {ENTAR + (ENTA. + .NTAR) + (ENT.. + .NTA. + ..TAR) + (EN... + .NT.. + ..TA. + ...AR) + (E.... + .N... + ..T.. + ...A. + ....R)} = 15=5⁺!² это равносильно пяти-значному треугольнику из шаров , где группы 15ти элементов при подсчёте имеют в себе 35ть единичных элементов,

по k=3 {5*1 + 4*2 + 3*3 + 2*4 + 1*5} =35=5⁺!³ трёх-значный тетраэдр. , (до конца не обдумал)

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

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

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

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

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

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

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

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

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

Число сочетаний с повторениями из $n$ по $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)!}}.

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

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