# degree of a polynomial over set-partitions

Denote $(x)_t = x(x-1)(x-2)\cdots(x-t+1)$ and fix some $t_1,\dots,t_n\in\mathbb{N}$. Now consider the polynomials $$f_n(x)=\sum_{\pi\in L[n]}(-1)^{\vert\pi\vert-1}(\vert\pi\vert-1)!\prod_{A\in\pi}(x)_{\sigma(A)}$$ where the sum extends over all non-empty set-partitions $L[n]$ of $[n]:=\{1,\dots,n\}$ and $\sigma(A)=\sum_{i\in A}t_i$.

Remark. $\#L[n]=B_n$ the Bell numbers.

Example. Take $n=3$. Then the set of set-partitions of $[3]$ reads $$L[3]=\{\{1,2,3\}, \{\{1,2\},\{3\}\}, \{\{1,3\},\{2\}\}, \{\{2,3\},\{1\}\}, \{\{1\},\{2\},\{3\}\}\}$$ and the polynomial becomes $$f_3(x)=(x)_{t_1+t_2+t_3}-(x)_{t_1+t_2}(x)_{t_3}-(x)_{t_1+t_3}(x)_{t_2}-(x)_{t_2+t_3}(x)_{t_1}+2(x)_{t_1}(x)_{t_2}(x)_{t_3}.$$

Conjecture. The polynomial $f_n$ is of degree $1+(t_1-1)+\cdots+(t_n-1)$ in the variable $x$. Is this true?

• For clarity, please edit the post to include a question mark. For example, end the post with "Is this conjecture true?". That way we know what part of the post you wish to address, even after subsequent edits. Gerhard "Make Post Interpretation More Robust" Paseman, 2016.12.06. Commented Dec 6, 2016 at 22:00
• What if it is not a question? A claim that I'm convinced is true. Conjectures are open to proofs or disproofs. Aren't they? Commented Dec 6, 2016 at 22:19
• This forum is a Question and Answer forum. It is not a problem forum, nor a place to entertain much discussion. The community hopes to build a database of well-written posts to help the mathematical communities of today and tomorrow. In my opinion (based on almost 7 years experience on this forum), your post could be improved to fit the needs of this forum by making the change. If you do not wish to post questions, that is up to you, but it is well written questions that are preferred here. Gerhard "MathOverflow Is Not A Catchall" Paseman, 2016.12.06. Commented Dec 6, 2016 at 22:35
• Okay. I edited in accord with your reasonable suggestion. Commented Dec 6, 2016 at 22:37
• The numbers $(-1)^{|\pi|-1}(|\pi|-1)!$ are coefficients of the Möbius function of the boolean lattice, so what you are doing is inverting some lattice function. Perhaps the details can be gleaned from Fedor's answer. Commented Dec 7, 2016 at 0:02

Yes, this is true. Let $M_1,\dots,M_n$ be disjoint sets, $|M_i|=t_i$, $M=\cup M_i$. Fix $s\in \{0,1,\dots,n-1\}$. Consider a permutation $w$ of the set $M$ which has exactly $|M|-s$ cycles. Assume that $w$ fixes each of the sets $\cup_{i\in A} M_i$, where $A$ is a part of a certain partition $\pi$ of the index set $[n]$. In this case we consider arbitrary cyclic order $F$ on the parts of $\pi$ and take a value $(-1)^{|\pi|-1}$, for each cyclic order, so totally we get $(-1)^{|\pi|-1}(|\pi|-1)!$. I claim that if $s<n-1$, then the sum of all such values equals 0, and if $s=n-1$, it is non-zero. First of all, it is what we have to prove: If you denote $x=-z$ and multiply your polynomial by $(-1)^{\sum t_i}$, the coefficient of $z^{\sum t_i-s}$ in the new polynomial $(-1)^{\sum t_i}f_n(-z)$ is exactly our sum, this follows from the Stirling numbers interpretations of the coefficients of $z(z+1)\dots (z+t-1)$.
Note that if $s<n-1$, then any fixed permutation $w$ has a stable set which is a union of several $M_i$'s (but not all of them). Choose, say, minimal such set of indices $I$ and partition all our values onto pairs by a very natural way: if $I$ was a separate part of $\pi$, unite it with the $F$-next part, else remove $I$ from the part $A$ containing $I$ (such $A$ exists by minimality) and make $I$ an $F$-previous part of a new cyclic order.
If $s=n-1$, this does not work for some permutations (which do not have such stable sets), but for them the sign is always the same (positive).