Lately I’ve been becoming more and more interested in enumerative combinatorics. Back in the days of contest math problems, I loved counting problems; they were one of my best strengths. Until the gorgeous sequence of talks by Richard Stanley at January’s Joint Meetings, I never really realized that enumerative combinatorics was of interest to “real, serious” mathematicians. Now that I know, I’ve been thinking more and more about these problems.
So last weekend at MathFest, I was pleased to learn of the following inequality involving binomial coefficients.
Let be positive integers. .
Apparently this inequality has been proven, but only by a lengthy and uninspiring computation involving estimating gamma functions. There is not yet a combinatorial proof. What do I mean by a combinatorial proof of an inequality? I mean an interpretation of each of the nested binomial coefficients as the number of objects in some set, and then an explicit bijection of one set with a proper subset of the other.
In this case, I am thinking of as counting the number of ways to choose a different (not necessary disjoint) b-element subsets of a set of c elements. For definiteness I can take the set of c elements to be , list the elements of a subset in increasing order, and list the subsets in lexicographical order. This suggests the following combinatorial formulation of the inequality.
Let be positive integers. Let S be the set of matrices with entries in . Let consist of those matrices in S for which the elements in each row are strictly increasing, and the rows are lexicographically strictly increasing. Let consist of those matrices in S for which the elements in each columns are strictly increasing, and the columns are lexicographically strictly increasing. Find an explicit bijection of of some proper subset of .
Haven’t cracked it yet, but I’m enjoying the attempt.