# combinations with repeated elements

###### Definition 1.

A $k$-combination with repeated elements chosen within the set $X=\{x_{1},x_{2},\ldots x_{n}\}$ is a multiset with cardinality $k$ having $X$ as the underlying set.

###### Note 2.

The definition generalizes the concept of combination with distinct elements.

###### Lemma 1.

Given $n,k\in\{0,1,2,\ldots\},n\geq k$, the following formula   holds:

 $\binom{n+1}{k+1}=\sum_{i=k}^{n}\binom{i}{k}.$
###### Proof.

The formula is easily demonstrated by repeated application of the Pascal’s Rule for the binomial coefficient. ∎

###### Theorem 1.

The number $C^{\prime}_{n,k}$ of the $k$-combinations with repeated elements is given by the formula:

 $C^{\prime}_{n,k}=\binom{n+k-1}{k}.$
###### Proof.

The proof is given by finite induction  (http://planetmath.org/PrincipleOfFiniteInduction).
The proof is trivial for $k=1$, since no repetitions can occur and the number of $1$-combinations is $n=\binom{n}{1}$.
Let’s then prove the formula is true for $k+1$, assuming it holds for $k$. The $k+1$-combinations can be partitioned in $n$ subsets as follows:

• combinations that include $x_{1}$ at least once;

• combinations that do not include $x_{1}$, but include $x_{2}$ at least once;

• combinations that do not include $x_{1}$ and $x_{2}$, but include $x_{3}$ at least once;

• combinations that do not include $x_{1}$, $x_{2}$,… $x_{n-2}$ but include $x_{n-1}$ at least once;

• combinations that do not include $x_{1}$, $x_{2}$,… $x_{n-2}$, $x_{n-1}$ but include $x_{n}$ only.

The number of the subsets is:

 $C^{\prime}_{n,k}+C^{\prime}_{n-1,k}+C^{\prime}_{n-2,k}+\ldots+C^{\prime}_{2,k}% +C^{\prime}_{1,k}$

which, by the inductive hypothesis and the lemma, equalizes:

 $\binom{n+k-1}{k}+\binom{n+k-2}{k}+\binom{n+k-3}{k}+\ldots+\binom{k+1}{k}+% \binom{k}{k}=\sum_{i=k}^{n+k-1}\binom{i}{k}=\binom{n+k}{k+1}.$

Title combinations with repeated elements CombinationsWithRepeatedElements 2013-03-22 17:43:17 2013-03-22 17:43:17 kfgauss70 (18761) kfgauss70 (18761) 8 kfgauss70 (18761) Definition msc 05A10 BinomialCoefficient