Nested binomials Let $t,d$ be positive integers and $n$ a parameter. The degree $td$ rational polynomial $p_{t,d}(n)={{ n \choose t} \choose d}$ obviously takes integral values for integral $n$ (not at all obvious from the expanded polynomial). It follows that it has a unique representation as a polynomial in binomial base ${n \choose k}$
$p_{t,d}(n)=\sum_{k=1}^{td} A_{t,d,k}{n \choose k}$,
where by a result of Polya, $A_{t,d,k}$ are integers. For examples, we have
${{n \choose 2} \choose 2}=\frac{n}{4}-\frac{n^2}{8}-\frac{n^3}{4}+\frac{n^4}{8}=3 {n \choose 3} + 3{n \choose 4}$
${{n \choose 2} \choose 3}={n \choose 3}+16{n \choose 4}+30{n \choose 5}+15{n\choose 6}$
${{n \choose 2} \choose 4}=\frac{n}{8}-\frac{n^2}{96}-\frac{19n^3}{96}+\frac{3n^4}{128}+\frac{n^5}{12}-\frac{n^6}{64}-\frac{n^7}{96}+\frac{n^8}{384}$
$=15{n \choose 4}+135{n \choose 5}+330{n \choose 6}+ 315 { n \choose 7}+105{n \choose 8}.$
It appears that the integral nested coefficients $A_{t,d,k}$ are unimodal and in fact log-concave. Numerical computations suggest this is always true. Is this always true ?
It seems further that if we let $f_{t,d}(x)=\sum_{k=1}^{td} A_{t,d,k}x^{td-k}$
then for $t$ even $f_{t,d}(x)$ are real rooted.
In all cases, $h_{t,d}(x):=f_{t,d}(x-1)$ is always log-concave and palimdormic eg $h_{2,4}(x)=15x^4+75x^3+15x^2$.
A similar result seems to hold also for all higher level nested binomial coefficients eg for level three,
${{{n \choose t} \choose d_1} \choose d_2}= \sum_{k=1}^{td_1d_2}A_{t,d_1,d_2,k} {n \choose k}.$
Transforming to binomial base It is known (OEIS A19538) that $x^n=\sum_{k=1}^n T(k,n){n \choose k}$ where $T(k,n)=k! S(n,k)$, and $S(n,k)$ is Stirling numbers of the second kind so that we have explicit formula for conversion to binomial base :
$\sum_{j=1}^na_jx^j=\sum_{k=1}^n b_k {x \choose k}$ where $b_k=\sum_{j=k}^n a_jT(k,j).$
$T(k,n)$ are positive, integral , and seemingly log-concave along columns and the obvious polynomials formed for each column has real and distinct roots which interlace as columns varies. A segment of $T$ looks like
$T=\begin{pmatrix} 1& 1 & 1& 1&1 & 1 & \ldots \cr 0 & 2 & 6 & 14 & 30 & 62 & \ldots \cr 0 & 0 & 6 & 36 & 150 & 540 & \ldots \cr 0 & 0 & 0 & 24 & 240 &1560 & \ldots \cr 0 & 0 & 0 & 0 & 120 & 1800 & \dots \cr 0 & 0 & 0 & 0 & 0 & 720 & \ldots \cr \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \dots \end{pmatrix}$
The log-concavity of $A_{t,d,k}$ probably just follows from those of $T(k,n)$.
Geometric meaning of the coefficients We are led to consider the nested binomials from a weight formula for enumerating subgraphs of $K_n$. Let $K_n$ be the complete graph on $n$ vertices, a subgraph $H$ is just a subset of the edges (so this ignore and excludes isolated points). We recently found a mass or weight formula for enumerating all such subgraphs. Each subgraph has an induced number of vertices $k=k(H)$ (eg. $k=3$ for triangle and $k=6$ for three disjoint edges). The weight formula for subgraphs of $K_n$ is
$ \sum_{H < K_n} {n \choose k} \frac{k!}{|Aut_k(H)|}=2^{n \choose 2},$
where $Aut_k(H)$ is the automorphism group of $H$ as a subgroups of $S_k$ of permutation of the induced vertices. This has a refinement if sum over subgraphs with a fixed number $d$ of edges. (Is this something well known ?)
$ \sum_{H < K_n, |H|=d} {n \choose k} \frac{k!}{|Aut_k(H)|}={{n \choose 2} \choose d}.$
If we now let $a_{2,d,k}$ be the sum over all $H<K_n$ on $d$ edges with the number of induced vertices $k(H)=k$ of the weights,
$(1) \;\;\; a_{2,d,k}:=\sum_{H<K_n,|H|=d,k(H)=k} \frac{k!}{|Aut_s(H)|},$
we will have
$(2) \;\; \sum_{k=1}^{2d} a_{2,d,k}{n \choose k}={{ n \choose 2} \choose d}.$
The upper limit $2d$ is to allow the maximal possible number of induced number of vertices on a union of $d$ disjoint edges but it still holds if $n<2d$ if we follow the usual convention that ${n \choose k}=0$ if $k<n$.
The weight formula (2) give a constraint on our geometric data $a_{2,d,k}$ but we then realize the constraint determine the data uniquely viewing ${{n \choose 2 } \choose d}$ as a polynomial in $n$ and expressing it in its unique binomial base. We must now have
$a_{2,d,k}=A_{2,d,k}$
so that can now rewrite (1) as
$\sum_{H<K_n,|H|=d,k(H)=k} \frac{k!}{|Aut_s(H)|}=A_{t,d,k},$
and viewed it as a refined weight formula since the RHS can be defined independently. Every thing still holds if we replace $2$ by $t$
$ \sum_{H < K_n, |H|=d} {n \choose k} \frac{k!}{|Aut_k(H)|}={{n \choose t} \choose d},$
where $H$ now is over isomorphism class of t-uniform hyper-subgraphs of $K_n$. The real rootedness of examples we computed for $f_{t,d}(x)$ and the palindromic nature of $h_{t,d}(x)$ lead us to guess it might always holds.
This seem very similar to a recently resolved difficult conjecture but may be this case (counting different things) is easier since it can de defined without the geometry, just based on properties of the Stirling numbers $T(k,n)$ ?
The weight formula is very useful when enumerating subgraphs especially uniform hyper-subgraphs of $K_n$, as a check that the enumeration is correct and complete.
We are lead to it via a Ramsey number functional which counts monochromatic 2-colored hyper-subgraphs.
