## Posts Tagged ‘enumeration’

### 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 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 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.