combinations with repeated elements

Definition 1.

A k-combination with repeated elements chosen within the set X={x1,x2,xn} 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 combinationMathworldPlanetmathPlanetmath is irrelevant.

Note 2.

The definition generalizes the concept of combination with distinct elements.

Lemma 1.

Given n,k{0,1,2,},nk, the following formulaMathworldPlanetmathPlanetmath holds:


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

Theorem 1.

The number Cn,k of the k-combinations with repeated elements is given by the formula:


The proof is given by finite inductionMathworldPlanetmath (
The proof is trivial for k=1, since no repetitions can occur and the number of 1-combinations is n=(n1).
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 x1 at least once;

  • combinations that do not include x1, but include x2 at least once;

  • combinations that do not include x1 and x2, but include x3 at least once;

  • combinations that do not include x1, x2,… xn-2 but include xn-1 at least once;

  • combinations that do not include x1, x2,… xn-2, xn-1 but include xn only.

The number of the subsets is:


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


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