A fourth proof
Last month I described three proofs of the formula for the number of ways to choose k objects from a set of n, if repetition is allowed and order is not significant; it is the same as the number of choices of k objects from a set of n+k−1, with repetition not allowed but order not significant.
If I needed evidence that I am getting older, here it is. I completely forgot the simplest proof of all, which I have known for a long time!
This is a bijective proof, that is, we show that the two sets have the same cardinality by establishing a bijection between them.
It works very simply. Given a set of k objects from the set {1,…,n+k−1}, since the order of choice is not important, we can label them arbitrarily; call the smallest element the first, the next smallest the second, and so on. Now we produce a selection (possibly with repetitions) of k objects from {1,…,n} as follows: keep the first object; subtract one from the second; subtract two from the third; … subtract k−1 from the kth.
The inverse bijection is described in the same way, but replacing “subtract … from” by “add … to”. In a selection with repetition, ties are unimportant.
Here is how it works out with n = 4, k = 2.
Pairs without repetition:
12, 13, 14, 15, 23, 24, 25, 34, 35, 45
Pairs with repetition:
11, 12, 13, 14, 22, 23, 24, 33, 34, 44
I said back then that different proofs have the advantage that they generalise in different ways. Here is an example, which I used when I taught elementary probability.
The British National Lottery involves choosing 6 numbers from {1,…49} (without replacement). Many people believe that the chance of having two consecutive numbers in the winning selection is very small. What is it really?
There are 
Bijections and permutations
“Bijective proofs” are sometimes called “combinatorial proofs”, a term I don’t like. If you have two sets An and Bn, with cardinalities f(n) and g(n), then one way to prove that f(n) = g(n) is to find a bijection between the two sets. But there are many others, no less combinatorial: for example, show that the generating functions for the sequences (f(n)) and (g(n)) are equal.
I think the advantage of bijective proofs (apart from the generic advantage of having another proof of something) lies in a different area. If you have a number of sets (say m of them) which you are trying to match up bijectively, the smallest amount of work you need to do is to find m−1 bijections forming a “minimal connector”, that is, the edges of a tree. But if you find extra bijections, you open up a new field of investigation.
Last year I wrote about Dima Fon-Der-Flaass, and mentioned the piece of work which brought him to my attention. To recap briefly: We have a finite partially ordered set P. Then there are bijections between the sets of down-sets, up-sets, and antichains in P, as follows:
- The set of maximal elements in a down-set is an antichain, and the set of elements lying below something in an antichain is a down-set (and these are inverse bijections).
- The set of minimal elements in an up-set is an antichain, and the set of elements lying above something in an antichain is an up-set (and these are inverse bijections).
- The complement of a down-set is an up-set, and vice versa.
Now, if we start at a particular down-set and go “round the triangle”, we obtain another down-set, not necessarily the same as the one we started with. So we have a permutation on the down-sets. Dima investigated this permutation, proving a “duality” for its cycles conjectured by Deza and Fukuda, and finding the lengths of the cycles in some cases.
More generally, if we have more than enough bijections to establish that our n sets are all of the same size, then we can compose them to find various permutations on one of the sets. Following Dima, I think it might be interesting to investigate these permutations in some cases.
One of the best worked-over areas for bijective proofs involves “Catalan objects”, things counted by the famous Catalan numbers. These include binary trees with n leaves; rooted plane trees with n edges; dissections of a convex n-gon; bracketings of a product of n factors; Dyck paths from the origin to (2n,0); and Young tableaux for a 2×n rectangle. There are so many known bijections here that we should be able to produce some interesting permutations!
Back to sampling
I have now given four proofs of the bijection between unordered samples without and with repetition.
You may recall that the third proof was a recursive proof inspired by the second. I have not checked whether the bijections produced by these two proofs are the same. Also, I think that the first and fourth proofs give the same bijection. (Would anyone like to check these assertions?)
However, the bijections produced by the second and fourth proofs are definitely different. Recall that in the second proof, we add k−1 “dummies” to the set {1,…,n}, to describe the repetitions in the sample. It seems natural to put the dummies at the end. If we do this in the case n = 4, k = 2, we obtain the following. (Remember that, for example, 15 translates into 11.)
Pairs without repetition:
12, 13, 14, 15, 23, 24, 25, 34, 35, 45
Pairs with repetition:
12, 13, 14, 11, 23, 24, 22, 34, 33, 44
So, applying one and the inverse of the other gives a permutation on the pairs of distinct elements which shifts cyclically the pairs with a given least element.
Problem. What happens for arbitrary n and k?
A small challenge
Here is a challenge you might enjoy, to find a bijective proof. In my post on the book Combinatorial Chance by David and Barton, I mentioned that the following sets of combinations of k from {1,…,n} (order unimportant, no repetition) have the same number of elements, for given m:
- the sets in which the difference between the greatest and least element is m;
- the sets in which the second largest element is m.
I have slightly re-formulated the observation, for simplicity.
Now the problem has two parts:
- Find a bijective proof.
- Formulate and prove an analogous result for combinations with repetition allowed.
Peter Cameron's Blog 