Combination

In combinatorics a combination of $n$ ${\ displaystyle n}$ $n$ by $k$ ${\ displaystyle k}$ $k$ called set $k$ ${\ displaystyle k}$ $k$ elements selected from a given set containing $n$ ${\ displaystyle n}$ $n$ various elements.

Sets that differ only in the sequence of elements (but not in composition) are considered the same, this combination differs from placements .

So, for example, sets (3-element combinations, subsets, $k=3$ ${\ displaystyle k = 3}$ $k = 3$ ) {2, 1, 3} and {3, 2, 1} of the 6-element set {1, 2, 3, 4, 5, 6} ( $n=6$ ${\ displaystyle n = 6}$ $n = 6$ ) are the same (while the placement would be different) and consist of the same elements {1,2,3}.

In general, a number showing how many ways you can choose $k$ ${\ displaystyle k}$ $k$ elements from a set containing $n$ ${\ displaystyle n}$ $n$ various elements standing at the intersection $k$ ${\ displaystyle k}$ $k$ diagonals and $n$ ${\ displaystyle n}$ $n$ th row of Pascal's triangle . ^[one]

Content

Number of Combinations

The number of combinations of $n$ ${\ displaystyle n}$ by $k$ ${\ displaystyle k}$ equal to binomial coefficient

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

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

At fixed $n$ ${\ displaystyle n}$ a generating function of a sequence of numbers of combinations ${\tbinom {n}{0}}$ ${\ displaystyle {\ tbinom {n} {0}}}$ , ${\tbinom {n}{1}}$ ${\ displaystyle {\ tbinom {n} {1}}}$ , ${\tbinom {n}{2}}$ ${\ displaystyle {\ tbinom {n} {2}}}$ , … is an:

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

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

The two-dimensional generating function of combination numbers is

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

Repeat Combinations

A combination with repetitions refers to sets in which each element can participate several times. In particular, the number of monotone non-decreasing functions from the set $\{1,2,\dots ,k\}$ ${\ displaystyle \ {1,2, \ dots, k \}}$ in many $\{1,2,\dots ,n\}$ ${\ displaystyle \ {1,2, \ dots, n \}}$ equal to the number of combinations with repetitions from $n$ ${\ displaystyle n}$ by $k$ ${\ displaystyle k}$ .

The number of combinations with repetitions from $n$ ${\ displaystyle n}$ by $k$ ${\ displaystyle k}$ equal to binomial coefficient

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 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)!}}.}

Evidence

Let there $n$ ${\ displaystyle n}$ types of objects, and objects of the same type are indistinguishable. Let there be unlimited (or sufficiently large, in any case, not less $k$ ${\ displaystyle k}$ ) the number of objects of each type. From this assortment we choose $k$ ${\ displaystyle k}$ objects; objects of the same type may occur in the sample; the order of selection does not matter. Denote by $x_{j}$ ${\ displaystyle x_ {j}}$ number of selected objects $j$ ${\ displaystyle j}$ type $x_{j}\geq 0$ ${\ displaystyle x_ {j} \ geq 0}$ , $j=1,2,\dots ,n$ ${\ displaystyle j = 1,2, \ dots, n}$ . Then $x_{1}+x_{2}+\dots +x_{n}=k$ ${\ displaystyle x_ {1} + x_ {2} + \ dots + x_ {n} = k}$ . But the number of solutions to this equation is easily calculated using "balls and partitions": each solution corresponds to the arrangement in a row $k$ ${\ displaystyle k}$ balls and $n-1$ ${\ displaystyle n-1}$ partitions so that between $(j-1)$ ${\ displaystyle (j-1)}$ and $j$ ${\ displaystyle j}$ the partitions were exactly $x_{j}$ ${\ displaystyle x_ {j}}$ balls. But such constellations are exactly ${\tbinom {n+k-1}{k}}$ ${\ displaystyle {\ tbinom {n + k-1} {k}}}$ , as required. ■

At fixed $n$ ${\ displaystyle n}$ generating function of numbers of combinations with repetitions from $n$ ${\ displaystyle n}$ by $k$ ${\ displaystyle k}$ is an:

\sum _{k=0}^{\infty }(-1)^{k}{-n \choose k}x^{k}=(1-x)^{-n}.

{\ displaystyle \ sum _ {k = 0} ^ {\ infty} (- 1) ^ {k} {- n \ choose k} x ^ {k} = (1-x) ^ {- n}.}

The two-dimensional generating function of the numbers of combinations with repetitions is:

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

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

Notes

↑ The amazing triangle of the great Frenchman.

Links

R. Stanley. Enumeration combinatorics. - M .: World, 1990.

[1] The amazing triangle of the great Frenchman.