1
$\begingroup$

I am doing some research in combinatorics, and I found that I have to consider the following binomial coefficient :

$$ \binom{\binom{i}{j}}{k} $$

(In fact, I have to take the product for fixed $i,k$ and odd $j$’s, but to make this product, I have to manipulate those coefficients, and I don’t know how.)

Is there a way to write it in terms of other binomial coefficients, power series, or other combinatorial tools?

$\endgroup$
1
  • 8
    $\begingroup$ We have $\dbinom{\dbinom{n}{j}}{k} = \sum\limits_{i=0}^{jk} a_i \dbinom{n}{i}$, where $a_i$ denotes the number of all $k$-element sets $\left\{S_1, S_2, \ldots, S_k\right\}$ of $j$-element subsets $S_1, S_2, \ldots, S_k$ of $\left\{1,2,\ldots,i\right\}$ satisfying $S_1 \cup S_2 \cup \cdots \cup S_k = \left\{1,2,\ldots,i\right\}$. This is folklore and easy to prove. I don't think the $a_i$ have any explicit algebraic descriptions, though. (Note that I stopped the sum at $i = jk$ simply to make it finite; it is easy to see that $a_i = 0$ for all $i > jk$.) $\endgroup$ Commented Jan 12, 2021 at 0:56

1 Answer 1

2
$\begingroup$

(In order that this question appears as answered I'm converting Darij Grinberg's comment into an answer.)

For $j$ and $k$ (that will remain fixed) in $\mathbb N$, and a set $X$, denote $\mathcal F(X):=\mathcal{P}_k\mathcal{P}_j(X)$, the set of all $k$-element sets $\mathcal U:=\{U_1,\dots,U_k\}$ of $j$-element subsets of $X$. Denote $\mathcal C(X)\subset \mathcal F(X)$ the set of those elements $\mathcal U$ of $\mathcal F(X)$ which are coverings of $X$, that is $\displaystyle \bigcup_{U\in \mathcal U}U =X$. Every $\mathcal U\in\mathcal F(X)$ is a covering of exactly one subset $Y$ of $X$, namely $Y:=\displaystyle \bigcup_{U\in \mathcal U}U$. Therefore $$\mathcal F(X)=\bigsqcup_{Y\subset X } \mathcal C(Y)$$ $$\mathcal C(X)=\Big(\bigcup_{x\in X } \mathcal F\big(X\setminus\{x\}\big)\Big)^c,$$ and note also that $$ \bigcap_{x\in Y} \mathcal F\big(X\setminus\{x\}\big)= \mathcal F\big(X\setminus Y\big).$$ As to cardinalities, if $|X|=n$, we have of course $\big|\mathcal F(X)\big|=\begin{pmatrix} n\\j \\ k \end{pmatrix} := \bigg( {{n\choose j}\atop k}\bigg) $, and, if we denote $\begin{bmatrix} n\\j \\ k \end{bmatrix}:=\big|\mathcal C(X)\big| $ we have from the above disjoint union $$\begin{pmatrix} n\\j \\ k \end{pmatrix}=\sum_{m=0}^n{n\choose m}\begin{bmatrix} m\\j \\ k \end{bmatrix},$$ which can be inverted giving $$\begin{bmatrix} m\\j \\ k \end{bmatrix}=\sum_{n=0}^m(-1)^{m-n}{m\choose n}\begin{pmatrix} n\\j \\ k \end{pmatrix}.$$ The latter, of course, can be seen as an instance of the inclusion-exclusion formula: $$\big|\mathcal C(X)\big| =\bigg|\Big(\bigcup_{x\in X } \mathcal F\big(X\setminus\{x\}\big)\Big)^c\bigg|=\sum_{Y\subset X}(-1)^{|Y|}\big|\mathcal F\big(X\setminus Y\big)\big|=\sum_{Y\subset X}(-1)^{|X\setminus Y|}\big|\mathcal F(Y)\big|$$

$\endgroup$
1
  • 1
    $\begingroup$ Nice organization of the proof! I had expected it to be more complicated. $\endgroup$ Commented Sep 15, 2021 at 0:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .