Return to Answer

This is the answer to the first question, see the long answer to Question 2 in 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}$.

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

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

This is the answer to the first question, see the long answer to Question 2 in 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}$.

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 labelled vertex in each component ($k_i$ correspond to the sizes of components.) Add a vertex 0 and join it with labelled 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}$.

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