Posts Tagged ‘ec’

Comparing Nested Binomial Coefficients

August 13, 2010

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 1<a<b<c be positive integers. \displaystyle \binom{\binom{c}{b}}{a}<\binom{\binom{c}{a}}{b}.

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 \displaystyle \binom{\binom{c}{b}}{a} 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 \{1,2,3,\ldots, c\}, 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 1<a<b<c be positive integers.  Let S be the set of a\times b matrices with entries in \{1,2,3,\ldots, c\}.  Let A consist of those matrices in S for which the elements in each row are strictly increasing, and the rows are lexicographically strictly increasing.  Let B 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 A of some proper subset of B.

Haven’t cracked it yet, but I’m enjoying the attempt.


%d bloggers like this: