Identity involving binomial coefficients and partitions

Question

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!

Answer 1

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.