# A combinatorial identity

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

• Combinatorial reformulation: consider all the trees $T$ on $\{0,1,\dots,K\}$ for which the vertices $1,2,\dots,p$ are in different components of $T\setminus \{0\}$. For each such a tree take a summand $(-K)^{\deg(0)-p}$. The sum equals $(K-2)!/(p-2)!$ for $p\geqslant 2$ and 0 for $p=0,1$. – Fedor Petrov Aug 15 '17 at 9:35

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}$.

• Thank you! This is a really cool argument, especially for me who doesn't have a lot of experiences in graph theory. I will mark this as the correct answer, but of course any further ideas and comments about question 2 are welcomed as well. – Honglu Aug 13 '17 at 18:41
• You need to talk to someone who's familiar with Volume 2 of Stanley. (This is more algebraic combinatorics than graph theory.) – Alexander Woo Aug 13 '17 at 23:10
• Sorry about my ignorance and thank you for pointing out the right words! I am thinking about asking around, and your comment definitely helps. – Honglu Aug 13 '17 at 23:58

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)$.

• Cool! I actually updated my question to include a more general identity that I want to prove. I kept thinking there is some generating function lurking behind, and I'm just looking at the coefficients. Any thoughts will be greatly appreciated. – Honglu Aug 14 '17 at 16:04

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*}

• Nice! I really learned a lot from all the answers and appreciate everybody's effort. In particular, this generating function method seems to have some other applications in our project. I got another quick question. Let $H_n=\sum\limits_{k=1}^n 1/k$. Do you know whether we can similarly describe the formal series $\sum_{n\geq 1} \dfrac{H_nn^n}{n!}z^n$ using functional equations just like your $T(z)$ and others? – Honglu Aug 15 '17 at 22:33
• Thank you. (1) The formal series $\sum_{n\geq 1}\frac{n^n}{n!}p(n) z^n$ can be expressed as a rational function of $T(z)$ if $p$ is a polynomial in $n$ and $\tfrac{1}{n}$. My first guess is that it will not be easy to treat the case $p(n)=H_n$ via Lagrange inversion. (2) $T(z)$ is certainly not "my" function. $T(z)=-W(-z)$ where $W$ is "Lambert's W-function", and $T(z)=z e^{T(z)}$ goes back to Eisenstein. – esg Aug 16 '17 at 17:57
• Would you mind telling me your real name by email? Because if we decide to post anything about this work in the future, we will acknowledge you (also Fedor and other people). I just temporarily added my email in my MO profile. We are still working on an ultimate combinatorial expression that includes all my questions as special cases. It's too long to post in a comment, but if you are interested, I will be glad to send it to you by email as well. Of course interests from other people will also be welcomed, just let me know in the comment or send me an email. – Honglu Aug 24 '17 at 16:09

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

• Not sure whether you get notifications from comments in other answers or not. To be sure I just repeat some messages here. I really appreciate all your answers here. Ultimately we want to simplify a bigger expression that includes the RHS of my question 2 as a special case. It's pretty long and currently still over my head. I don't know if you have the time and the interest to take a look. But in case you do, you are welcomed to send me an email (in my profile). – Honglu Aug 24 '17 at 19:55