combinations with repeated elements

Definition 1.

A $k$-combination with repeated elements chosen within the set $X=\{x_1,x_2,\mathrm{\dots }{x}_n\}$ is a multiset with cardinality $k$ having $X$ as the underlying set.

Note 1.

The definition is based on the multiset concept and therefore the order of the elements within the combination is irrelevant.

Note 2.

The definition generalizes the concept of combination with distinct elements.

Lemma 1.

Given $n\mathrm{,}k\mathrm{\in }\mathrm{\{}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{,}\mathrm{2}\mathrm{,}\mathrm{\dots }\mathrm{\}}\mathrm{,}n\mathrm{\ge }k$, the following formula holds:

$$\left(\genfrac{}{}{0pt}{}{n+1}{k+1}\right)=\sum _{i=k}^n\left(\genfrac{}{}{0pt}{}{i}{k}\right).$$

Proof.

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

Theorem 1.

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

$$C_{n,k}^{\prime }=\left(\genfrac{}{}{0pt}{}{n+k-1}{k}\right).$$

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=\left(\genfrac{}{}{0pt}{}{n}{1}\right)$.
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_{n,k}^{\prime }+C_{n-1,k}^{\prime }+C_{n-2,k}^{\prime }+\mathrm{\dots }+C_{2,k}^{\prime }+C_{1,k}^{\prime }$$

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

$$\left(\genfrac{}{}{0pt}{}{n+k-1}{k}\right)+\left(\genfrac{}{}{0pt}{}{n+k-2}{k}\right)+\left(\genfrac{}{}{0pt}{}{n+k-3}{k}\right)+\mathrm{\dots }+\left(\genfrac{}{}{0pt}{}{k+1}{k}\right)+\left(\genfrac{}{}{0pt}{}{k}{k}\right)=\sum _{i=k}^{n+k-1}\left(\genfrac{}{}{0pt}{}{i}{k}\right)=\left(\genfrac{}{}{0pt}{}{n+k}{k+1}\right).$$

∎