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$ Jan 12 at 0:56
3
$\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$ 2 days ago

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.