Solution Sketch

Use linearity of expectation to reduce to a single node, i.e. "what is the expected number of trees where the node with label 1 has degree ~d_i~". Now use the fact that in the bijection between Prüfer sequences and labelled trees, if the node ~i~ has degree ~d_i~ in the tree, it shows up ~d_i-1~ times in the corresponding Prüfer sequence.

Counting the number of valid Prüfer sequence can be done with generating functions using NTT. Note that you need only consider the first ~N~ terms of the generating function, so you can take multiplication mod ~x^N~.

Time Complexity: ~\mathcal O(N\log^2 N + M)~.

Solution 1

Let ~\mathcal S~ denote the set of labeled trees whose degrees belong to ~D = \{d_1,d_2,\ldots,d_M\}~. Define the generating functions $$\displaystyle \begin{align*} F(x,\mathbf t) &= \sum_{i=1}^M \frac{t_i}{d_i!} x^{d_i} \\ G(x,\mathbf t) &= \sum_{i=1}^M \frac{t_i}{(d_i-1)!} x^{d_i-1} \end{align*}$$ where ~\mathbf t = (t_1,\ldots,t_M)~ are indeterminants.

Let ~S(x,\mathbf t)~ denote the exponential generating function for ~\mathcal S~, where ~[x^n]S(x,\mathbf t)~ is a polynomial, and ~[\mathbf t^{\mathbf\alpha}][x^n]S(x,\mathbf t)~ is the number of trees with ~n~ total vertices, ~\alpha_i~ of which have degree ~d_i~.

By standard generating function theory, the average number of vertices with degree ~d_i~ over all trees with ~N~ vertices given by $$\displaystyle \mu_i:=\frac{\left.\frac{\partial}{\partial t_i} N![x^N] S(x,\mathbf t)\right|_{\mathbf t = \mathbf 1}}{N![x^N]S(x,\mathbf 1)} = \frac{\left.\frac{\partial}{\partial t_i}[x^N] S(x,\mathbf t)\right|_{\mathbf t = \mathbf 1}}{[x^N]S(x,\mathbf 1)}.$$

To compute this value, let ~S^\bullet(x,\mathbf t)~ denote the number of rooted labeled trees whose degrees belong to ~D~. By standard generating function theory, we have $$\displaystyle [x^N]S(x,\mathbf t) = \frac 1 N[x^N]S^\bullet(x,\mathbf t). $$ so it suffices to compute ~[x^N]S^\bullet(x,\mathbf t)~.

We can simplify again: if we delete the root node, we are left with trees where every node has ~\{d_1-1,d_2-1,\ldots,d_M-1\}~ children. Call this class ~\mathcal T^\bullet~, and let ~T^\bullet(x,\mathbf t)~ be its generating function. Now we have $$\displaystyle \begin{align*} T^\bullet(x,\mathbf t) &= x G(T^\bullet(x,\mathbf t),\mathbf t) \\ S^\bullet(x,\mathbf t) &= x F(T^\bullet(x,\mathbf t),\mathbf t). \end{align*}$$ As ~N\geq 2~, we can apply LIFT to obtain $$\displaystyle \begin{align*} [x^N]S^\bullet(x,\mathbf t) &= [x^N]x F(T^\bullet(x,\mathbf t),\mathbf t) \\ &= [x^{N-1}] F(T^\bullet(x,\mathbf t),\mathbf t) \\ &= \frac{1}{N-1}[x^{N-2}]G(x,\mathbf t)^{N-1}F'(x,\mathbf t). \end{align*}$$ where ~F'(x,\mathbf t) = \frac{\partial}{\partial x}F(x,\mathbf t)~. In particular, we need ~N-1\geq 1~ so we can apply the generalized form of LIFT to get the final equality.

Note that $$\displaystyle F'(x,\mathbf t) = \frac{\partial}{\partial x}F(x,\mathbf t) = \sum_{i=1}^M \frac{t_i}{(d_i-1)!} x^{d_i-1} = G(x,\mathbf t), $$ so we get $$\displaystyle [x^N]S^\bullet(x,\mathbf t) = \frac{1}{N-1}[x^{N-2}]G(x,\mathbf t)^N. $$ Substituting, we obtain $$\displaystyle \mu_i = \frac{\left.\frac{\partial}{\partial t_i}[x^{N-2}]G(x,\mathbf t)^N\right|_{\mathbf t = \mathbf 1}}{[x^{N-2}]G(x,\mathbf 1)^{N}}. $$ Note the denominator can be easily computed via ~O(\log N)~ applications of NTT, where each iteration we discard higher order terms. This takes ~O(N\log^2 N + M)~.

The tricky part is efficiently computing the numerator: as coefficient extraction and taking partial derivatives with respect to ~t_i~ commute, we can apply the product rule to get $$\displaystyle \frac{\partial}{\partial t_i}[x^{N-2}]G(x,\mathbf t)^N = N[x^{N-2}]\left(\frac{\partial}{\partial t_i}G(x,\mathbf t)\right)G(x,\mathbf t)^{N-1} $$ Now note that $$\displaystyle \begin{align*} \left.\frac{\partial}{\partial t_i} G(x,\mathbf t)\right|_{\mathbf t = \mathbf 1} &= \frac{1}{(d_i-1)!} x^{d_i-1} \\ \end{align*}$$ hence $$\displaystyle \begin{align*} \left.\frac{\partial}{\partial t_i}[x^{N-2}]G(x,\mathbf t)^N\right|_{\mathbf t = \mathbf 1} &= N[x^{N-2}]\left(\frac{x^{d_i-1}}{(d_i-1)!}\right)G(x,\mathbf 1)^{N-1} \\ &= \frac{N}{(d_i-1)!}[x^{N-d_i-1}]G(x,\mathbf 1)^{N-1} \end{align*}$$ Now note that we can compute all of the coefficients of ~G(x,\mathbf 1)^{N-1}~ in ~O(\log N)~ applications of NTT, where each iteration we discard higher order terms. This too takes ~O(N\log^2 N + M)~, and the final coefficient extraction can be done in ~O(M)~.

Thus we can compute the ~\mu_i~ in ~O(N\log^2 N + M)~.

Solution 2

We give an alternate derivation for the generating function.

Let ~X_{u,d}~ be a random variable that is 1 if the node with label ~u~ has degree exactly ~d~, and 0 otherwise. We wish to compute ~\mathbb E\left[\sum_{u=1}^N X_{u,d_i}\right]~ for ~i = 1, 2, \ldots, M~. Now by linearity of expectation, we have $$\displaystyle \mathbb E\left[\sum_{u=1}^N X_{u,d_i}\right] = \sum_{u=1}^N\mathbb E[X_{u,d_i}]. $$ Note that each ~X_{u,d_i}~ is identically distributed: to see this, for ~v\neq u~, note that the permutation ~\tau_{u,v}~ swapping the labels of ~u~ and ~v~ induces a bijection between labelled trees where the node with label ~u~ has degree ~d~, and labelled trees where the node with label ~v~ has degree ~d~, for all ~d~.

Thus we get $$\displaystyle \mathbb E\left[\sum_{u=1}^N X_{u,d_i}\right] = N\cdot\mathbb E[X_{1,d_i}], $$ so it remains to compute ~\mathbb E[X_{1,d_i}]~.

Recall that labelled trees on ~N~ vertices are in bijection with Prüfer sequences. In particular, if a given label ~u~ appears ~d~ times in the Prüfer sequence, then the node with label ~u~ has degree ~d+1~ in the corresponding tree.

Thus we want to count the number of sequences ~\{1, \ldots, N\}^{N - 2}~ where the first element appears ~d_i-1~ times, and every other element appears ~d_1 - 1, d_2 - 1, \ldots, d_{M-1} - 1~, or ~d_M - 1~ times. $$\displaystyle \frac{N!}{(d_i-1)!}[x^{N-1-d_i}]\left(\sum_{j=1}^M\frac{x^{d_j-1}}{(d_j-1)!}\right)^{N-1}$$ which is precisely ~\frac{N!}{(d_i-1)!}[x^{N-d_i-1}]G(x,\mathbf 1)^{N-1}~, where ~G(x,\mathbf 1)~ is as defined above. The total number of trees is then given by summing the previous expression over all ~d_i~; this gives an ~O(N\log^2 N + M)~ solution.

To see this is equivalent to the previous expression, the total number of trees is $$\displaystyle \sum_{i=1}^M \frac{N!}{(d_i-1)!}[x^{N-1-d_i}] \left(\sum_{j=1}^M\frac{x^{d_j-1}}{(d_j-1)!}\right)^{N-1} = N![x^{N-2}]\left(\sum_{j=1}^M\frac{x^{d_j-1}}{(d_j-1)!}\right)^N = N![x^{N-2}]G(x,\mathbf 1)^N $$ hence we get $$\displaystyle \mu_i = \frac{N}{(d_i-1)!}\cdot\frac{[x^{N-1-d_i}]G(x,\mathbf 1)^{N-1}}{[x^{N-2}]G(1,\mathbf 1)^N} $$ which agrees with our previous computation.