19
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Just a vague idea : Why not investigate some particular polynomials (Hermite,Laguerre...) with coefficients like yours ? $\endgroup$
    – Erik Satie
    Sep 3, 2021 at 12:51
  • $\begingroup$ @ErikSatie I took a look at the coefficients, and what I see essentially are two-term recurrences, and coefficients that don't contain nested binomial coefficients. Sure, what I could do is think about, for example recurrences of some sort. For example, binomial coefficients satisfy some kind of recurrence, probably. So putting binomials themselves as the indices of the recurrence suggests an idea. $\endgroup$ Sep 3, 2021 at 15:50

1 Answer 1

10
+50
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ I see! Yes, this proof makes sense for sure, +1. I've understood it completely, and to be fair it made for a standard approach, since the operation going from one set to the other , via removal/addition of an element was quite natural. Perhaps we can pull this off with $\binom{\binom{n}{b}}{c}$ vs $\binom{\binom{n}{b-1}}{c+1}$ as well with the same element-removal principle. I'll take a look. $\endgroup$ Sep 7, 2021 at 2:36
  • $\begingroup$ @TeresaLisbon I believe I figured out how to use this idea for the general case too but it is past midnight here, so I'll post tomorrow (provided that my proof survives until the morning :-) ) $\endgroup$
    – fedja
    Sep 7, 2021 at 4:19
  • $\begingroup$ It will survive till the morning, see you tomorrow! $\endgroup$ Sep 7, 2021 at 4:26
  • $\begingroup$ @TeresaLisbon It looks like it did, but, please, check it and, of course, ask questions if anything is unclear :-) $\endgroup$
    – fedja
    Sep 7, 2021 at 13:00
  • 1
    $\begingroup$ @TeresaLisbon thinking about this from the analysis point of view (I'm an analyst first!) will also intrigue me. Yeah, it would be interesting to get it via $\Gamma$-functions too, though even in that case I would prefer something "short and inspiring" to a tedious brute force computation, if possible :-) $\endgroup$
    – fedja
    Sep 9, 2021 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.