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+k1}{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}_{n2}$ but include ${x}_{n1}$ at least once;

•
combinations that do not include ${x}_{1}$, ${x}_{2}$,… ${x}_{n2}$, ${x}_{n1}$ but include ${x}_{n}$ only.
The number of the subsets is:
$${C}_{n,k}^{\prime}+{C}_{n1,k}^{\prime}+{C}_{n2,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+k1}{k}\right)+\left(\genfrac{}{}{0pt}{}{n+k2}{k}\right)+\left(\genfrac{}{}{0pt}{}{n+k3}{k}\right)+\mathrm{\dots}+\left(\genfrac{}{}{0pt}{}{k+1}{k}\right)+\left(\genfrac{}{}{0pt}{}{k}{k}\right)=\sum _{i=k}^{n+k1}\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  20130322 17:43:17 
Last modified on  20130322 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 