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 combination is irrelevant.
Note 2.
The definition generalizes the concept of combination with distinct elements.
Lemma 1.
Given n,k∈{0,1,2,…},n≥k, the following formula holds:
(n+1k+1)=n∑i=k(ik). |
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=(n+k-1k). |
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=(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:
C′n,k+C′n-1,k+C′n-2,k+…+C′2,k+C′1,k |
which, by the inductive hypothesis and the lemma, equalizes:
(n+k-1k)+(n+k-2k)+(n+k-3k)+…+(k+1k)+(kk)=n+k-1∑i=k(ik)=(n+kk+1). |
∎
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 |