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.

### Like this:

Like Loading...

*Related*

Tags: binomial coefficients, combinatorics, ec, enumeration

This entry was posted on August 13, 2010 at 1:29 am and is filed under Misc. Problems. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply