Consider a set $N$ with elements $n\_1, n\_2, \dots, n\_k$ which are distinct integers. Introduce the notation $N\_{i=1,2,\dots,s}$ for the $s$ blocks of a set partition of $N$. Consider a supplementary integer $n\_{k+1}$.


We have the identity


$(\sum\_{i=1}^{k+1} n\_i -k)^{k-1}= \sum\_{\text{set partitions } N\_i \text{ of } N } \prod\_{l=1}^s ((\sum\_{n\_j \in N\_l} n\_j)−|\_l|+1)^{|N\_l|-1}(\_{k+1}−1)!/(\_{k+1}−)!$


I have proven the identity for $=1,2,…,8$ analytically (using a symbolic manipulation program) and for $=9,10,11$
numerically. On the right hand side, we have expanded the polynomial in $n\_{k+1}$
into falling factorials according to the number $s$ of blocks in the set partition $N\_i$. The number $k$ is a positive integer.


The identity arises in the context of the theory of conjugacy class sums of the symmetric group.


I have proven parts of this identity, e.g. for particular values of $n\_{k+1}$, and so on. I have tried various inductions (on the number of variables $k$ as well as on the number of parts s in the partition) and derivations, though not exhaustively.


Is there a known or unknown analytic proof of this identity ? Is there a standard and/or efficient strategy to prove the identity ?


(Edited for clarity following a first comment and fixed a typo indicated in a second comment.)



Proof of a combinatorial identity for a sum over partitions of sets giving rise to a symmetric polynomial?
The notation and framing of the problem are not optimal, because the $n\_i$'s being integers is a bit of a distraction.


Let $[k]:=\{1,\ldots,k\}$, and let ${\rm Part}\_k$ be the set of set partitions of $[k]$. We also use $|A|$ to denote the cardinality of a set $A$.
Let $x\_1,\ldots,x\_k$ and $y$ be formal variables.


The problem is to prove
$$
(1+y+x\_1+\cdots+x\_k)^{k-1}=\sum\_{\Theta\in{\rm Part}\_k}
y(y-1)\cdots(y-|\Theta|+2)\times\prod\_{J\in\Theta}
\left(1+\sum\_{i\in J}x\_i\right)^{|J|-1}\ .
$$


I think this is true because the matrices made of [Stirling numbers](https://en.wikipedia.org/wiki/Stirling_number) of first and second kinds are inverses of each other.


To recover the original notations set $x\_i=n\_i-1$ and $y=n\_{k+1}-1$.




---


**Update:** Here is a proof.


Use the matrix-tree/Cayley formula for counting trees according to specified vertex-degrees (see, e.g., [these notes](https://math.berkeley.edu/~mhaiman/math172-spring10/matrixtree.pdf) by Mark Haiman), which reads
$$
z\_1\cdots z\_n(z\_1+\cdots+z\_n)^{n-2}=\sum\_{T}\prod\_{\{i,j\}\in T}z\_i z\_j\ ,
$$
where the sum is over trees $T$ on the set $[n]$ which connect all vertices.
Edges are treated as subsets $\{i,j\}$ of $[n]$ of cardinality 2.


Take $n=k+1$, $z\_1=1$, $z\_2=x\_1,\ldots,z\_n=x\_k$.
Then we get a sum over rooted forests
$$
(1+x\_1+\ldots+x\_k)^{k-1}=\sum\_{F,R}\frac{\prod\_{\{i,j\}\in F}x\_i x\_j}{\prod\_{i\in[k]\backslash R} x\_i}\ ,
$$
where $F$ is the set of edges and $R$ is the set of roots (exactly one per connected component).
Now instead of using it once, globally on $[k]$, use the previous identity *locally* in each $J$. This gives
$$
\prod\_{J\in\Theta}\left(1+\sum\_{i\in J}x\_i\right)^{|J|-1}
=\sum\_{\Pi\le \Theta}\sum\_{F,R|\Pi}\frac{\prod\_{\{i,j\}\in F}x\_i x\_j}{\prod\_{i\in[k]\backslash R} x\_i}\ ,
$$
where the sum is restricted to forests whose components form the partition $\Pi$ which refines the fixed partition $\Theta$.


**Remark 1:**
The last step we will need is related to Möbius inversion in the partition lattice.
For $y=-1$ the multiplying factor
$y(y-1)\cdots(y-|\Theta|+2)$ is the Möbius function $\mu(\Theta,\mathbf{1})$. For reference, the partition lattice is the set ${\rm Part}\_k$ together with the partial order $\Theta\_1\le\Theta\_2$ when the blocks of $\Theta\_1$ are contained in blocks of $\Theta\_2$, i.e., $\Theta\_1$ is refinement or further subdivision of $\Theta\_2$.
The minimal element is $\mathbf{0}$, the partition made of singletons. The maximal element is $\mathbf{1}$, the partition made the single block $[k]$. The möbius matrix $(\mu(\Theta\_1,\Theta\_2))\_{\Theta\_1,\Theta\_2}$ with rows and columns indexed by set partitions, is the inverse of the matrix given by the indicator function of the statement $\Theta\_1\le \Theta\_2$.


Now note that the right-hand side of the identity to be established is
$$
RHS=\sum\_{\Theta\in{\rm Part}\_k}
\sum\_{\Pi\le\Theta}
y(y-1)\cdots(y-|\Theta|+2)
\times\left(\sum\_{F,R|\Pi}\frac{\prod\_{\{i,j\}\in F}x\_i x\_j}{\prod\_{i\in[k]\backslash R} x\_i}\right)\ ,
$$
$$
=\sum\_{\Pi\in{\rm Part}\_k}
\sum\_{\Theta\ge\Pi}y(y-1)\cdots(y-|\Theta|+2)
\times\left(\sum\_{F,R|\Pi}\frac{\prod\_{\{i,j\}\in F}x\_i x\_j}{\prod\_{i\in[k]\backslash R} x\_i}\right)\ ,
$$
$$
=\sum\_{\Pi\in{\rm Part}\_k}\left(
\sum\_{F,R|\Pi}\frac{\prod\_{\{i,j\}\in F}x\_i x\_j}{\prod\_{i\in[k]\backslash R} x\_i}\right)\times
\sum\_{\Theta\ge\Pi}y(y-1)\cdots(y-|\Theta|+2)\ .
$$
Now, we have
$$
\sum\_{\Theta\ge\Pi}y(y-1)\cdots(y-|\Theta|+2)=
\frac{1}{y+1}\sum\_{j=1}^{|\Pi|}S(|\Pi|,j)\ (y+1)y(y-1)\cdots((y+1)-j+1)\ ,
$$
where the $S(\cdot,\cdot)$ are the Stirling numbers of the second kind. We also ``contracted'' $\Pi$ so blocks become points.
By a [well known property of the Stirling numbers](https://en.wikipedia.org/wiki/Stirling_number#Expansions_of_falling_and_rising_factorials),
$$
\sum\_{j=1}^{|\Pi|}S(|\Pi|,j)\ (y+1)y(y-1)\cdots((y+1)-j+1)=(y+1)^{|\Pi|}\ ,
$$
so
$$
RHS=\sum\_{\Pi\in{\rm Part}\_k}\left(
\sum\_{F,R|\Pi}\frac{\prod\_{\{i,j\}\in F}x\_i x\_j}{\prod\_{i\in[k]\backslash R} x\_i}\right)\times (y+1)^{|\Pi|-1}\ ,
$$
$$
=\frac{1}{x\_1\cdots x\_k(y+1)}
\sum\_{\Pi\in{\rm Part}\_k}
\sum\_{F,R|\Pi}(y+1)^{|\Pi|}\prod\_{i\in R}x\_i\prod\_{\{i,j\}\in F}x\_ix\_j\ .
$$
This clearly is a sum over trees on a set with $n=k+1$ elements. Using the matrix tree/Cayley formula again (but in the reverse direction) with $z\_1=y+1$, $z\_2=x\_1,\ldots,z\_n=x\_k$, and cleaning up, we get the desired result $(1+y+x\_1+\cdots+x\_k)^{k-1}$.


**Remark 2:** Since this problem showed up in a study of cycle structures of permutations, one could mention the following. Forests give set partitions by taking connected components. Permutations give set partitions by taking the supports of the disjoint cycles of the permutation. So there is nothing surprising in forests featuring in the proof above. However, there is also a *direct* relation between forests and permutations. Writing a permutation as a minimal product of transpositions gives a forest. The correspondence is not 1:1 of course, and this has been studied by Dénes and other, see my previous answer
<https://math.stackexchange.com/questions/3535217/in-how-many-ways-can-a-permutation-cycle-be-decomposed-as-a-product-of-transposi/3536747#3536747>


