*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 *n ^{k}* 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.

#### First proof

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, … *n*th 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 *n*th 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 .

#### Second proof

This proof more directly chooses *k* distinct objects from a set of *n*+*k*−1. The set consists of the given objects A_{1}, … A_{n}, together with *k*−1 “dummy” objects X_{1}, … X_{k−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 X_{i}, then we repeat the *i*th 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, A_{1}A_{3}X_{1}X_{2} is translated first into A_{1}A_{1}A_{3}X_{2}, and then into A_{1}A_{1}A_{1}A_{3}; for A_{1}A_{3}X_{1}X_{3}, the first step is the same but at the second step we obtain A_{1}A_{1}A_{3}A_{3}.

It is slightly more difficult to show that this gives the required bijection.

#### Third proof

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.