combinations with repeated elements
The definition generalizes the concept of combination with distinct elements.
Given , the following formula holds:
The formula is easily demonstrated by repeated application of the Pascal’s Rule for the binomial coefficient. ∎
The number of the -combinations with repeated elements is given by the formula:
The proof is given by finite induction (http://planetmath.org/PrincipleOfFiniteInduction).
The proof is trivial for , since no repetitions can occur and the number of -combinations is .
Let’s then prove the formula is true for , assuming it holds for . The -combinations can be partitioned in subsets as follows:
combinations that include at least once;
combinations that do not include , but include at least once;
combinations that do not include and , but include at least once;
combinations that do not include , ,… but include at least once;
combinations that do not include , ,… , but include only.
The number of the subsets is:
which, by the inductive hypothesis and the lemma, equalizes:
|Title||combinations with repeated elements|
|Date of creation||2013-03-22 17:43:17|
|Last modified on||2013-03-22 17:43:17|
|Last modified by||kfgauss70 (18761)|