# Identity involving binomial coefficients and partitions

Working on a problem in the symmetric group I have stumbled upon the following equation:

$$\sum_{\substack{\pi=(1^{c_1},2^{c_2},\ldots,n^{c_n})\\\textrm{partition of }n}}(-1)^{n-\sum_{i=1}^nc_i}\frac{n!}{\prod_{i=1}^ni^{c_i}c_i!}\left(\sum_{\substack{\eta=(1^{b_1},2^{b_2},\ldots,k^{b_k})\\\textrm{partition of }k}}\prod_{j=1}^k{c_j\choose b_j}\right)^\ell=0,$$ where $$n,k$$ and $$\ell$$ are positive integers and $$1\le k,\ell\le n-1.$$ (Here, $$\pi=(1^{c_1},2^{c_2},\ldots,n^{c_n})$$ means that $$n=1\cdot c_1+2\cdot c_2+\cdots +c_n\cdot n$$.)

I have two questions. First, whether this equality has appeared somewhere. (I have checked the book(s) of Stanley on Enumerative combinatorics, but with no luck.) Second, given $$n$$ and $$k$$, I am intersted on the smallest value of $$\ell$$, where the equality above is not satisfied. For instance, when $$n:=43$$ and $$k:=13$$, with a computer computation one can check that the equality above is satisfied FOR EACH element in $$\{1,2,3,4,5,6\}$$ and $$\ell:=7$$ is the first time where this equality is not satisfied. However, I have no clue in how to get my hands on this value!

If $$A\subset B$$, $$b$$ is a permutation (self-bijection) of $$B$$, and $$a$$ a permutation of $$A$$, we say that $$a$$ is a subpermutation of $$b$$ if any cycle of $$a$$ is a cycle of $$b$$. Your sum is the sum of $${\rm sign}(b)$$ taken over all permutations $$b$$ of $$B=\{1,2,\ldots,n\}$$ and all subpermutations $$a_1,\ldots,a_\ell$$ of $$b$$ with $$|a_1|=|a_2|=\ldots=|a_\ell|=k$$ (here $$|a_i|:=|A_i|$$ where $$a_i$$ is a permutation of $$A_i\subset B$$). Let us fix $$A_1,\ldots,A_\ell$$, and consider the partition $$B=\sqcup_{i=1}^m C_i$$ of $$B$$ generated by $$A_1,\ldots,A_\ell$$. Note that every set $$C_j$$ must be invariant under $$b$$ and those $$a_i$$'s for which $$C_j\subset A_i$$ (since for every $$x\in C_j$$ the $$b$$-orbit of $$x$$ is contained in each set $$A_i$$ containing $$x$$, thus in their intersection which is just $$C_j$$), and the restrictions of $$b$$ and corresponding $$a_i$$'s to $$C_j$$ coincide.

If there exists $$j$$ such that $$|C_j|>1$$, fix two elements $$u\ne v$$ and partition all tuples $$(b,a_1,\ldots,a_k)$$ onto couples multiplying $$b$$ and all $$a_i$$'s with $$A_i\supset C_j$$ by the transposition of $$u$$ and $$v$$. This changes the parity of $$b$$, preserves the required property, and so proves that the corresponding part of your sum equals 0.

If $$|C_j|=1$$ for all $$j$$, then $$b$$ and all $$a_i$$'s must be identical permutations and this paet of your sum equals 1.

Therefore your question is equivalent to the following:

do there exist sets $$A_1,\ldots,A_\ell\subset B$$ with $$|B|=n$$, $$|A_i|=k$$ for all $$i$$ such that for all $$u\ne v$$ in $$B$$ there exists $$j\in \{1,\ldots,\ell\}$$ such that $$A_j$$ contains exactly one of $$u$$ and $$v$$ (in other words, the partition of $$B$$ generated by $$A_i$$'s is the partition onto $$n$$ singletons)? Or, another reformulation: when the edges of the complete graph $$K_n$$ may be covered by $$\ell$$ complete bipartite graphs $$K_{k,n-k}$$?

Let me explain, for example, why for $$n=43$$, $$k=13$$ and $$\ell=6$$ such 6 sets $$A_1,\ldots,A_6$$ do not exist. For each element $$u\in B$$ consider the set $$T(u)\subset \{1,2,3,4,5,6\}=\{i: u\in A_i\}$$. Such sets are mutually distinct, thus $$6\cdot 13=\sum_u|T(u)|\geqslant 1\cdot 0+6\cdot 1+15\cdot 2+21\cdot 3$$ (at most one set $$T(u)$$ is empty, at most 6 sets have size 1 etc), that is not true.

• Your formulation in terms of sets $A_i$ (or if you prefer with the covering of the complete graph) is actually where I have started from. This insights are great but it seems to me to be difficult to use this to pin down the value of $\ell$ and I was hoping that the formula above could help. Mar 22 '21 at 13:00
• I would be very much surprised if this extremal combinatorics question may be resolved by such formula. Mar 22 '21 at 14:18