Someone posted a modified variant of ABC 180 F here before and asked for help solving it. The task went as follows: given $$$n$$$ and $$$\ell$$$, count the number of labeled graphs on $$$n$$$ vertices such that no vertex has a degree exceeding 3, there is no cycle in any connected component (i.e. the graph is a forest) and the largest connected component has exactly $$$\ell$$$ vertices.

I wrote a rather long comment explaining how to solve it. I hit "post" and...

the blog was gone.

To whoever was the author: please don't do this. It's very frustrating to put effort into writing an explanation only to discover that it had been completely in vain. Even if you already got an answer from elsewhere, other users might enjoy reading the solution. It was not the case here, but especially don't delete/hide your blog if there already are answers in the comments. This way you're effectively just erasing other people's work. That sort of thing can really put me and others off from helping people in the comments altogether.

So that my effort wouldn't be completely wasted, I decided to post the contents of my comment here as a separate blog. (In theory, this might have been some ongoing contest or interview problem. But it really is an obvious modification to the AtCoder problem and I sort of believe the author. Besides, all of this is rather standard.)

Let's first learn to count the number of labeled trees with $$$k$$$ vertices where each vertex has degree at most 3. We'll use Prüfer sequences. A Prüfer sequence of a tree with $$$k$$$ vertices is an array consisting of $$$k-2$$$ entries. Importantly, each tree corresponds to exactly one sequence and vice versa. Also, every vertex $$$u$$$ appears in the sequence exactly $$$\mathrm{deg}(u) - 1$$$ times.

So we need to count the number of arrays consisting of $$$k - 2$$$ entries such that every vertex appears in the array 0, 1 or 2 times. We will do that with DP: let $$$\mathrm{dp}[i][j]$$$ be the number of sequences where we have already placed the first $$$i$$$ vertices that have length $$$j$$$ now. We'll try to place the $$$i$$$-th vertex now. A sequence of $$$j$$$ elements has $$$j + 1$$$ "slots" where we could insert the instances of the $$$i$$$-th vertex. So,

• $$$\mathrm{dp}[i][j]$$$ contributes once to $$$\mathrm{dp}[i + 1][j]$$$;
• $$$(j + 1)$$$ times to $$$\mathrm{dp}[i + 1][j + 1]$$$;
• $$$\binom{j + 1}{2}$$$ times to $$$\mathrm{dp}[i + 1][j + 2]$$$.

You can calculate this DP in $$$O(n^2)$$$ time and you'll be interested in the value of $$$\mathrm{dp}[k][k - 2]$$$ for every $$$k$$$. Let's call this value $$$f(k)$$$.

Now to the original problem. I'm going to change it slightly and say we instead need to find the answer where the largest connected component can be up to $$$\ell$$$. This doesn't really change anything as you can calculate the answer for "up to $$$\ell$$$" and then from it subtract the answer for "up to $$$\ell - 1$$$".

Let $$$\mathrm{dp}[i]$$$ be the number of forests with $$$i$$$ vertices where the largest connected component has size up to $$$\ell$$$ and every degree is up to 3. Suppose we have such a forest. We are now going to add to it another tree with $$$k$$$ vertices. There are $$$f(k)$$$ ways to choose a tree. But how many ways are there to add this new tree to the forest? Keep in mind that the indices for this new tree can be "interleaved" with the old forest. E.g. vertices 1 and 3 could be in the old forest and vertices 2 and 4 in the new one. To avoid double-counting, we will assume that the vertex with index $$$i + k$$$ belongs to the new tree. Among the other $$$i + k - 1$$$ vertices, we choose $$$i$$$ of them to assign to the old forest and $$$k - 1$$$ to assign to the new. Therefore, $$$\mathrm{dp}[i]$$$ contributes $$$f(k) \binom{k + i - 1}{i}$$$ times to $$$\mathrm{dp}[i + k]$$$.

In total, the complexity will be $$$O(n\ell)$$$.