Strange inequality involving *nested* binomial coefficients and combinatorial interpretation

Question

Recently, I solved a question that asked for a geometric proof of the identity $\binom{\binom{n}{3}}{2} < \binom{\binom{n}{2}}{3}$ and I did it here using the combinatorial interpretation of lines and triangles in an $n$-gon, and exploiting the symmetry of these line-triangle configurations to provide an injective (and non-surjective) map from a set with cardinality $\binom{\binom{n}{3}}{2}$ to a set of cardinality $\binom{\binom{n}{2}}{3}$.

This brought me to the more general question :

Suppose that $b>c$. Then, for all $n$, is the following true? $$\binom{\binom{n}{b}}{c} < \binom{\binom{n}{c}}{b}$$

(Note : we define $\binom{k}{l} = 0$ if $l>k$).

I want a proof of this, but I've just left some avenues open so that others can explore them below.

To break the suspense, this identity is true, but I've actually never seen a proof of it, so here goes.

---

Gamma function

I looked here for some details, and apparently a "lengthy,uninspiring computation involving Gamma functions" is required. Nevertheless, I couldn't quite find a reference to this computation : so I'd love one. Having said that , if someone can write up an (lengthy, uninspiring etc.) argument that involves Gamma functions, I'd be delighted. To provide some details on the link, we have : $$ \binom{n}{k} = \frac{n!}{(n-k)!k!} = \frac{\Gamma(n+1)}{\Gamma(n-k+1)\Gamma(k+1)} $$

and therefore, nested binomial coefficients will involve nested Gamma functions, at which point I wasn't quite able to work my way through.

---

Combinatorial interpretation

The same document as above provides a telling combinatorial interpretation :

$\binom{\binom{n}{b}}{c}$ is the number of ways of choosing a subset of $c$ elements ,from the set of subsets of $b$ elements of $\{1,2,...,n\}$.

which it then twists into :

$\binom{\binom{n}{b}}{c}$ is the number of $b \times c$ matrices with entries in $\{1,...,n\}$, such that the elements are strictly increasing along rows, and the rows, interpreted as vectors , are strictly lexicographically increasing.

So perhaps one can work with these combinatorial objects. On the other hand, one can see if something around what I did with the $n$-gons can be generalized, I struggled to do so.

Short note : binomial basis expansion

Note also, that the linear-algebraic approach that I proposed in my answer (to give an algebraic proof of the nested binomial identity) can probably work here (i.e. writing the nested binomial coefficients in the polynomial basis $\binom{n}{k},0<k\leq bc$) : but the coefficients when one uses the binomial basis are quite complicated, see here. Note that both the nested binomial coefficients are polynomials of degree $bc$ in $n$, so one can try to see if something works out via binomial basis expansions.

---

Alternate definitions

See if alternate definitions/generalizations of the binomial coefficient are helpful, like this one. Note that if we can make the binomial coefficient into a nice continuous-parameter function, then we can investigate these properties using real analytic methods.

EDIT : This document of Marko Riedel contains details of the Egorychev (Егорычев) method, which is basically a complex-analytic representation of the binomial coefficients. Anyone is free to use any of the identities available here, and I thank Marko for creating this useful list.

The basic problem here is the nesting of the coefficients, so any fundamental operation that simplifies the nesting (converting the nesting into an operation that is easier to understand) will be appreciated, either in the comments or as a partial answer.

Finally, further comments on inequalities involving further nestings like $\binom{\binom{\binom{n}{a}}{b}}{c}$ and so on will be appreciated as well.

Answer 1

There is a cute argument for $b=c+1$ though I don't know how to pull it through in the general case.

Let $U$ be the set of ordered $c+1$-tuples of sets of cardinality $c$ in which no set repeats. Then, obviously, $|U|=(c+1)!{{n\choose c}\choose c+1}$. Let $V$ be the set of ordered $c$-tuples of sets of cardinality $c+1$ in which no set repeats. Then $|V|=c!{{n\choose c+1}\choose c}$. Now take any element of $V$, i.e., an ordered family of sets $A_1,\dots,A_{c}$. Take any $a_1\in A_1$ ($c+1$ choices). Suppose that $a_1\in A_1,\dots,a_k\in A_k$ are already chosen. Then we want to choose $a_{k+1}\in A_{k+1}$ so that $a_{k+1}\ne a_j$ and $A_{k+1}\setminus \{a_{k+1}\}\ne A_j\setminus\{a_j\}$ for all $j=1,\dots,k$. Suppose that we have $\ell$ prohibitions of the first type. Then, if we honor them, the prohibitions of the second type for the corresponding sets will be honored automatically (if $a_j\in A_{k+1}$ and we don't remove it, then surely $A_{k+1}\setminus \{a_{k+1}\}\ne A_j\setminus\{a_j\}$. The remaining $k-\ell$ sets introduce at most one prohibition of the second type each, so we have $\le k$ prohibitions total. Thus we have $\ge c+1-k$ choices for $a_{k+1}$. Once we run the whole procedure, the reduced sets $A_j$ listed in the same order and the set $\{a_1,\dots,a_c\}$ listed last will constitute an element of $U$ and each element of $V$ will generate $\ge(c+1)!$ different elements of $U$ (by different choices of $a_1,\dots,a_c$. On the other hand, each element of $U$ can be obtained from at most $c!$ elements of $V$ (that is the number of ways to distribute the elements of the last $c+1$-st set among the first $c$. This immediately gives a non-strict inequality you want. To make it strict, you need to assume $c>1$ and $n\ge c+1$ (otherwise you have equality), in which case the ordered sequence of sets $A_j=\{1,2,\dots,c+1\}\setminus\{j\}$ has fewer than $c!$ distribution options (none at all, really) resulting in a legitimate element of $V$.

Edit (the general case)

In this case it will be convenient to define $U$ as the set of all ordered $b$-tuples of sets of cardinality $c$ such that the sets are pairwise different (as sets), the first $c$ sets are unordered, and the last $b-c$ sets are ordered. Then $|U|=b!(c!)^{b-c}{{n\choose c}\choose b}$. Let $V$ be the same as before (ordered $c$-tuples of unordered subsets of cardinality $b$ in which the sets are pairwise different), so $|V|=c!{{n\choose b}\choose c}$.

Now let $\langle A_1,\dots, A_c\rangle$ be an element of $V$. We want to remove $b-c$ elements $a_{j,1},a_{j,2},\dots,a_{j,b-c}$ from $A_j$ and form $b-c$ new ordered sets $B_k=\langle a_{1,k},a_{2,k},\dots, a_{c,k}\rangle$ ($k=1,\dots,b-c$) to get an element of $U$.

To this end start with choosing $a_{1,1},\dots,a_{1,b-c}\in A_1$ in an arbitrary way, which gives $b(b-1)\dots(b-c+1)$ choices. Now, when choosing $a_{k+1,1}\in A_{k+1}$ for $k\ge 1$, add to the standard prohibitions $a_{k+1,1}\ne a_{j,1}$, $A_{k+1}\setminus\{a_{k+1,1}\}\ne A_j\setminus\{a_{j,1}\}$ ($j\le k$), which exclude at most $k$ elements just as before, the prohibitions $a_{k+1,1}\ne a_{1,m}$ ($m>1$), which exclude additional $b-c-1$ elements at most, leaving $c+1-k$ choices as before. These additional prohibitions guarantee that the set $B_1=\{a_{1,1},a_{2,1},\dots, a_{c,1}\}$ does not contain any of the elements $a_{1,m}$ ($m>1$) and, therefore, will be different from every set $B_m$ ($m>1$) as an unordered set and we still have $c!$ choices.

Having constructed $B_1$, we construct $B_2$ with the standard restrictions $a_{k+1,2}\ne a_{j,2}$, $A_{k+1}\setminus\{a_{k+1,1},a_{k+1,2}\}\ne A_j\setminus\{a_{j,1},a_{j,2}\}$ ($j\le k$) and additional restrictions $a_{k+1,2}\ne a_{1,m}$ but now with $m>2$. This gives $c!$ choices again, and so on. Thus, from each element of $V$, we get $b(b-1)\dots(b-c+1) (c!)^{b-c}$ distinct elements of $U$. The recovery of an element of $V$ from an element of $U$ is now possible in just one way, if at all, which, again, gives a non-strict inequality. I leave it to you to figure out when and how it becomes strict in this case.