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).$$

∎

Title	combinations with repeated elements
Canonical name	CombinationsWithRepeatedElements
Date of creation	2013-03-22 17:43:17
Last modified on	2013-03-22 17:43:17
Owner	kfgauss70 (18761)
Last modified by	kfgauss70 (18761)
Numerical id	8
Author	kfgauss70 (18761)
Entry type	Definition
Classification	msc 05A10
Related topic	BinomialCoefficient