A combinatorial identity

Question

I hope this is a suitable MO question. In a research project, my collaborator and I came across some combinatorial expressions. I used my computer to test a few numbers and the pattern was suggesting the following equation for fixed integers $K\geq n>0$.

$$\dfrac{K!}{n!K^{K-n}}\sum\limits_{ \begin{subarray}{c} k_1+\dotsb+k_{n}=K \\ k_i \geq 1 \end{subarray}} \prod\limits_{i=1}^n \dfrac{k_i^{k_i-2}}{(k_i-1)!}=\displaystyle {K-1\choose n-1}.$$

We tried to think of a proof but failed. One can probably move these $K!, n!$ to the right and rewrite the RHS, or maybe move $K!$ into the summation to form combinatorial numbers like $K\choose k_1,k_2,\dotsc,k_n$. We don't know which is better.

The questions are:

1. Anyone knows a proof for this identity?
2. In fact the expression that appears in our work is $\sum\limits_{ \begin{subarray}{c} k_1+\dotsb+k_{n}=K \\ k_i \geq 1 \end{subarray}} \sigma_p(k_1,\dotsc,k_n) \prod\limits_{i=1}^n \dfrac{k_i^{k_i-2}}{(k_i-1)!}$, where $p$ is a fixed integer and $\sigma_p(\dotsc)$ is the $p$-th elementary symmetric polynomial. The equation in the beginning simplifies this expression for $p=0,1$. Is there a similar identity for general $p$?

----------Update----------

Question 2 is perhaps too vague, and I'd like to make it a bit more specific. Probably I should have written this down in the beginning, but I feared this is too long and unmotivated. But after seeing people's skills, I'm very tempted to leave it here in case somebody has remarks. In fact, question 2 partly comes from the effort to find a proof for the following (verified by computer).

$$ \frac{1}{K!} \prod_{r=1}^{K} (r+1 -x)= \sum_{n=1}^K \frac{(-1)^n}{n!} \left[ \sum_{p=0}^n K^{n-p} \prod_{r=1}^p (x +r-4) \left( \sum\limits_{ \begin{subarray}{c} k_1+\dotsb+k_{n}=K \\ k_i \geq 1 \end{subarray}} \sigma_p(k_1,\dotsc,k_{n}) \prod\limits_{i=1}^n \dfrac{k_i^{k_i-2}}{(k_i-1)!} \right) \right], $$ Where $x$ is a fixed number (in our case, an integer).

Answer 1

This is the answer to the first question, I wrote a long answer to Question 2 as a separate answer.

Note that $A:=\sum_{k_i>0,k_1+\dots+k_n=K}\frac{K!}{n!k_1!\dots k_n!} \prod k_i^{k_i-1}$ is a number of forests on the ground set $\{1,2,\dots,K\}$ having exactly $n$ connected components and with a marked vertex in each component ($k_i$ correspond to the sizes of components.) Add a vertex 0 and join it with the marked vertices. Then we have to count the number of trees on $\{0,1,\dots,K\}$ in which $0$ has degree $n$. Remember that the sum of $z_0^{d_1-1}\dots z_K^{d_K-1}$ over all trees on $\{0,\dots,K\}$, where $d_i$ is degree of $i$, equals $(z_0+\dots+z_K)^{K-1}$. Substitute $z_{1}=\dots=z_K=1$ and take a coefficient of $z_0^{n-1}$. It is $\binom{K-1}{n-1}K^{K-n}$.

Answer 2

Here's another proof. We first rewrite the identity (by setting $k_i=j_i+1$) as $$ \sum_{j_1+\cdots +j_n=K-n}\prod_{i=1}^n \frac{(j_i+1)^{j_i-1}}{j_i!} = n\frac{K^{K-n-1}}{(K-n)!}. \tag{1} $$

Let $F(x)$ be the formal power series satisfying $F(x)= e^{xF(x)}$. It is well known (and easily proved, e.g., by Lagrange inversion) that $$F(x)^n = \sum_{j=0}^\infty n(j+n)^{j-1}\frac{x^j}{j!}.\tag{2}$$ In particular, $$F(x) = \sum_{j=0}^\infty (j+1)^{j-1}\frac{x^j}{j!}.$$ So the left side of $(1)$ is equal to the coefficient of $x^{K-n}$ in $F(x)^{n}$, which by $(2)$ is equal to the right side of $(1)$.

Answer 3

Here is a generating-function proof of your conjectured identity (and an answer to question 2).

The main ingredient is a formula for the appearing symmetric sums.

Let $T(z)$ (the ``tree function'') be the formal power series satisfying $T(z)=z\,e^{T(z)}$.

If $F$ is a formal power series the coefficients of $G(z):=F(T(z))$ are given by (Lagrange inversion) $$[z^0]G(z)=[z^0] F(z) \mbox{ , } [z^k]G(z)=\tfrac{1}{k} [y^{k-1}] F^\prime(y)\,e^{ky} =[y^k](1-y)F(y)\,e^{ky}\mbox{ for } k\geq 1\;.$$ In particular (as is well known) $$T(z)=\sum_{n\geq 1}\frac{n^{n-1}}{n!}z^n \;\mbox{ and }\; \frac{T(z)}{1-T(z)}=\sum_{n\geq 1}\frac{n^{n}}{n!}z^n$$ Thus $T(z)\left(1+\frac{t}{1-T(z)}\right)=\sum_{n\geq 1} \frac{(1+tn)n^{n-1}}{n!}$. Therefore \begin{align*}S_{p,n}(K):&=\sum_{{k_1+\ldots +k_n=K \atop k_i\geq 1}} \sigma_p(k_1,\ldots,k_n)\prod_{i=1}^n \frac{k_i^{k_i-1}}{k_i!}\\ &=[t^p]\sum_{k_1+\ldots +k_n=K \atop k_i\geq 1} \prod_{i=1}^n \frac{(1+tk_i) k_i^{k_i-1}}{k_i!}\\ &=[t^p z^K]\, T(z)^n \left(1+\frac{t}{1-T(z)}\right)^n \end{align*} and $$S_{p,n}(K)={n \choose p} [z^K]\frac {T(z)^n}{(1-T(z))^p}={n \choose p}[y^K]\,y^n\, \frac{(1-y)}{(1-y)^p}\,e^{Ky}\;\;\;\;\;(*)$$

Now consider the sum ($m:=x-4$) $$R(K,m):=\sum_{n=0}^K\frac{(-1)^n}{n!}\bigg[\sum_{p=0}^n K^{n-p}\,\left(\prod_{r=1}^p (m+r)\right) S_{n,p}(K)\bigg]$$ Since $K\geq 1$ the sum remains unchanged if we start the summation at $n=0$ (all $S_{0,p}(K)$ are $0$). Using that and $(*)$ gives \begin{align*} R(K,m):&=\sum_{n=0}^K\frac{(-1)^n}{n!}\bigg[\sum_{p=0}^n K^{n-p}\,\left(\prod_{r=1}^p (m+r)\right) S_{n,p}(K)\bigg]\\ &=[y^K]\,(1-y) \sum_{n=0}^K\frac{(-1)^n}{n!}\sum_{p=0}^n K^{n-p}\,p!{m+p \choose p}{n \choose p}\frac{y^n}{(1-y)^p}\,e^{Ky}\\ &=[y^K]\,(1-y) \sum_{p=0}^K\sum_{n=p}^K\frac{(-1)^n}{(n-p)!} K^{n-p}{m+p \choose p}\frac{y^n}{(1-y)^p}\,e^{Ky}\\ &=[y^K]\,(1-y) \sum_{p=0}^K {m+p \choose p}\frac{(-1)^p y^p}{(1-y)^p}\bigg[\sum_{n=p}^K\frac{(-1)^{n-p}}{(n-p)!} K^{n-p}y^{n-p}\,e^{Ky}\bigg]\\ &=[y^K]\,(1-y) \sum_{p=0}^K {m+p \choose p}\frac{(-1)^p y^p}{(1-y)^p}\bigg[1 +\mathcal{O}(y^{K-p+1})\bigg]\\ \end{align*} where $\mathcal{O}(y^{K-p+1})$ denotes a formal power series which is a multiple of $y^{K-p+1}$.
Taking into account the respective factors $y^p$ the terms in these series do not contribute to the coefficient $[y^K]$. Therefore

\begin{align*} R(K,m)&=[y^K]\,(1-y) \sum_{p=0}^K {m+p \choose p}\frac{(-1)^p y^p}{(1-y)^p}\\ &=[y^K]\,(1-y) \sum_{p\geq 0} {m+p \choose p}\frac{(-1)^p y^p}{(1-y)^p}\\ &=[y^K]\,(1-y) \left(\frac{1}{1+\tfrac{y}{1-y}}\right)^{m+1}\\ &=[y^K]\,(1-y)^{m+2}\\ &=(-1)^K\,{m+2 \choose K},\,\mbox{ as desired }. \end{align*}

Answer 4

Here is the answer to Question 2. It may be probably simplified.

Denote $y=3-x$, then we rewrite your identity as $$\binom{y+K-2}K=\frac{(y-1)y(y+1)\dots (y+K-2)}{K!}=c_0\binom{y}0+c_1\binom{y}1+\dots+c_K\binom{y}K,$$ where $$c_p=p!\sum_{n=p}^K(-K)^{n-p}\frac1{n!}\sum\limits_{ \begin{subarray}{c} k_1+\dotsb+k_{n}=K \\ k_i \geq 1 \end{subarray}} \sigma_p(k_1,\dotsc,k_{n}) \prod\limits_{i=1}^n \dfrac{k_i^{k_i-2}}{(k_i-1)!}.$$ On the other hand, by Vandermonde--Chu identity we have $$\binom{y+K-2}K=\sum_{i=2}^{K}\binom{y}i\binom{K-2}{K-i},$$ so your identity is equivalent to the formula $$ \sum_{n=p}^K(-K)^{n-p}\frac{K!}{n!}\sum\limits_{ \begin{subarray}{c} k_1+\dotsb+k_{n}=K \\ k_i \geq 1 \end{subarray}} \sigma_p(k_1,\dotsc,k_{n}) \prod\limits_{i=1}^n \dfrac{k_i^{k_i-2}}{(k_i-1)!}=\frac{K!}{p!}\binom{K-2}{K-p}, $$ I multiplied both parts by $K!/p!$. Note that $$ \frac{K!}{n!}\sum\limits_{ \begin{subarray}{c} k_1+\dotsb+k_{n}=K \\ k_i \geq 1 \end{subarray}} \sigma_p(k_1,\dotsc,k_{n}) \prod\limits_{i=1}^n \dfrac{k_i^{k_i-2}}{(k_i-1)!} $$ is a number of the trees $T$ on $\{0,1,\dots,K\}$ such that degree of 0 equals $n$ and $p$ vertices in different components of $T\setminus\{0\}$ are marked. Indeed, if these components $A_1,\dots,A_n$ are enumerated (this corresponds to the multiple $n!$) and $i$-th component $A_i$ has $k_i$ vertices, then we have $\frac{K!}{k_1!\dots k_n!}$ ways to choose $A_i$, $\sigma_p(k_1,\dotsc,k_{n}) $ ways to mark $p$ vertices in different components, $k_i^{k_i-1}$ ways to make a tree on $A_i$ and choose a vertex in $A_i$ joined with 0.

Note that each (out of $\binom{K}p$ sets) set of $p$ marked vertices makes the same contribution to the sum. So, we may suppose that the marked set is $\{1,2,\dots,p\}$ and we have to prove that the sum of $(-K)^{n-p}$ over admissible trees (where the tree $T$ is admissible if $1,2,\dots,p$ are in different components of $T\setminus \{0\}$) equals $\frac1{\binom{K}p}\frac{K!}{p!}\binom{K-2}{K-p}=(p-1)p\dots (K-2)$.

We start to prove this from the case $p=0$, $p=1$, where the restriction that $1,2,\dots,p$ are in different components of $T\setminus \{0\}$ disappears. Then the sum $z_0^{n-1}z_1^{d_1-1}\dots z_K^{d_K-1}$, $d_i=\deg(i)$, over all trees on $\{0,\dots,K\}$ equals, as is well known and easy to prove, to $(z_0+\dots+z_K)^{K-1}$. Substituting $z_0=-K$, $z_1=\dots=z_K=1$ we get the result.

Now we deal with the more involved case $p\geqslant 2$. Denote $K=p+m$ and consider the variables $z_0,z_1,\dots,z_p,z_{p+1},\dots$ (infinitely many for simplicity of notations). Denote $s=z_0+z_1+\dots$, write $\sigma_i$ for the $i$-th elementary symmetric polynomial of $z_{p+1},z_{p+2},\dots$. Denote $\varphi_0=1$, $\varphi_m=s\varphi_{m-1}+(p-1)p\dots (p+m-2)\sigma_m$ for $m\geqslant 1$. I claim that the sum of $z_0^{n-p}z_1^{d_1-1}\dots z_{p+m}^{d_{p+m}-1}$ over all admissible trees equals $\varphi_m(z_0,z_1,\dots,z_{p+m},0,0,\dots)$.

Note that this implies our claim, as follows from the substitution $z_0=-K=-p-m,z_1=\dots=z_{p+m}=1$.

The proof is on induction in $m$. Base $m=0$ is clear. For the induction step, look at coefficients of any specific monomial $z_0^{n-p}z_1^{d_1-1}\dots z_{p+m}^{d_{p+m}-1}$. Consider two cases:

1) $d_i=1$ for a certain index $i\in \{p+1,\dots,p+m\}$, without loss of generality $i=p+m$. This corresponds to the case when $p+m$ has degree 1, such a vertex may be joined with any of other vertices, and removing corresponding edge we get a tree (it remains admissible) on $\{0,1,\dots,K-1\}$. This corresponds to the summand $s\varphi_{m-1}$: namely, $z_j\varphi_{m-1}$ corresponds to the edge between $p+m$ and $j$; $j=0,1,\dots,p+m-1$.

2) $d_{p+1},\dots,d_{p+m}$ are greater than 1. Then they are all equal to 2, since the degree of the whole monomial equals $m$. In this case there are $p(p+1)\dots (p+m-1)$ admissible trees (well, they are all admissible for such a choice of degrees and we may either apply the above formula for all trees, or prove it by induction, or as you wish). It remains to prove that the coefficient of $z_{p+1}\dots z_{p+m}$ in the function $\varphi_m$ equals $p(p+1)\dots (p+m-1)$. Since $\varphi_m=s\varphi_{m-1}+(p-1)p\dots (p+m-2)\sigma_m$, it is equivalent to proving that the coefficient of $z_{p+1}\dots z_{p+m}$ in $s\varphi_{m-1}$ equals $p(p+1)\dots (p+m-1)-(p-1)p\dots (p+m-2)=mp(p+1)\dots(p+m-2)$. We should take some $z_j$, $p+1\leqslant j\leqslant p+m$, from the multiple $s=\sum z_i$, and for each choice of $j$ we have a coefficient of $z_j^{-1}\cdot z_{p+1}\dots z_{p+m}$ in $\varphi_{m-1}$ equal to $p(p+1)\dots(p+m-2)$ - by induction (base $m-1=0$ is clear).