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 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,k \in \{0,1,2,\ldots\},n \ge 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'_{n,k}$ of the $k$ -combinations with repeated elements is given by the formula: $$ C'_{n,k}=\binom{n+k-1}{k}. $$

Proof. The proof is given by finite induction.
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'_{n,k}+C'_{n-1,k}+C'_{n-2,k}+\ldots +C'_{2,k}+C'_{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}. $$