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!


1 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.

  • $\begingroup$ 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. $\endgroup$ Mar 22, 2021 at 13:00
  • $\begingroup$ I would be very much surprised if this extremal combinatorics question may be resolved by such formula. $\endgroup$ Mar 22, 2021 at 14:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.