In how many ways can you choose a sample of size k from n distinguishable objects?
As is well known, the answer depends on the sampling rules: Does the order of selection matter, or not? Are items allowed to be selected more than once, or not?
Three of the answers are very easy. If order is significant, the answer is nk if repetition is allowed, and the “falling factorial” n(n−1)···(n−k+1) if not. If repetition is not allowed and order is not significant, the answer is the preceding number divided by k!, which is the binomial coefficient .
The fourth case is the most difficult. The answer is the “rising factorial” n(n+1)···(n+k−1) divided by k!, which is the binomial coefficient .
Rosemary and I have assembled three quite different proofs of the last formula for your festive entertainment.
This one I regard as the “standard” proof. A selection of k items from n with repetition allowed is specified by giving the numbers of occurrences of the first, second, … nth object; these numbers must add up to k. We can choose a specification as follows.
Take a row of n+k−1 boxes. Choose n−1 of them, and put “barriers” in these; then k empty boxes remain. Now put copies of the first object in the boxes before the first barrier; copies of the second object in the boxes between the first and second barrier; … and copies of the nth object in the boxes after the last barrier. This gives a selection. Conversely, any selection can be decoded into positions for the barriers. So the required number is .
This proof more directly chooses k distinct objects from a set of n+k−1. The set consists of the given objects A1, … An, together with k−1 “dummy” objects X1, … Xk−1, whose purpose is to tell us about repeats.
Choose a subset of k elements from this set, and order it with the As first (in order), and then the Xs (in order).
If the chosen set of size k consists only of As, then we have a selection with no repeats. If there is just one dummy element, say Xi, then we repeat the ith object in the list. If there are more than one dummy, we repeat the procedure, working from left to right through the set of dummies.
For example, A1A3X1X2 is translated first into A1A1A3X2, and then into A1A1A1A3; for A1A3X1X3, the first step is the same but at the second step we obtain A1A1A3A3.
It is slightly more difficult to show that this gives the required bijection.
This proof is by induction.
One reason for having more than one proof is that different proofs may give different extra information. It follows from the preceding proof that the number of selections which involve just m distinct objects is , since the As chosen in the first step are all the distinct objects which we see.
Now the Vandermonde convolution shows that
where the sum is over all m for which the binomial coefficients are non-zero. So in order to prove the formula, it would suffice to have a direct proof of the formula in the second paragraph.
This can be done as follows. Clearly is the number of ways of choosing the m objects which actually appear. Once they are chose, we have to select k from this set of m in such a way that all of the m objects actually appear. This can be done by first including each object once in the selection, and then choosing k−m more (with repetitions allowed). Since the numbers are smaller than in the original instance, the induction hypothesis guarantees that the number of ways of doing this is .
I leave the problem of starting the induction to the reader.
in the third para, you mean $n^k$ not $nk?$
Thanks – now fixed.
Another proof is to apply Ehrhart’s theorem to the simplex given by the equation
Of course, this is a bit of a sledgehammer, but Ehrhart’s theorem subsumes
many “combinatorial reciprocity” theorems. Another example is Richard
Stanley’s theorem on acyclic orientations of graphs.
Thanks. Nice — but as you realised, I was trying to avoid the heavier sledgehammers.