Hunting the Beast — Deon Nicholas

Problem

A graph is called functional if every node has exactly one outgoing edge, and no edge points from a node to itself (no self-loops).

Given a functional graph on $n$ nodes, we can choose a set of $m$ special nodes. A selection is good if every node in the graph is either special, or reachable from a special node in 1 or more steps.

Given $n$ and $m$ $(1 \leq m \leq n \leq 10^6)$ , count the number of good selections, summed over all possible functional graphs on $n$ nodes, modulo $998244353$ .

Initial Observations

[From experience] the graph is a collection of cycles with trees attached to them.
Combinatorics + DP + recursion?
$n$ choose $m$ — does it matter which $m$ you choose? (By symmetry, probably not.)
$1 \leq m \leq n \leq 10^6$ , so we need $O(n)$ or $O(n \log n)$ .
This seems hard.
All leaves have to be special.
[Exploit symmetry / constraints] A lot of symmetry here — does some formula simplify?
Flows?

IdeaLeaves and cycles, direct recursion

Key Observation

Any graph where each node has out-degree 1 is a collection of cycles with trees hanging off them.

Draw from Experience

I knew this structure from prior problems — but you can also [Draw a Picture] and [Examine Examples] to convince yourself: keep following the out-edges from any node and you must eventually revisit a node. That's a cycle.

Key Observation

If any leaf (a node with no incoming edges) is not special, the selection is bad: nothing can reach a leaf, so every leaf must be special.

Key Observation

Symmetrically, if some component is a pure cycle (no trees attached), then at least one node on that cycle must be special — otherwise the whole component is unreachable.

At this point the problem still seemed really hard given the $O(n \log n)$ constraint.

Relax the Constraints

Ignore the $O(n \log n)$ requirement — can I solve this at all, in $O(n^2)$ or $O(n^3)$ , to get a feel?

Draw from Experience

Problems like this usually work by deciding what happens to node $n$ , then recursing on the graph with $n-1$ nodes.

This leads to a recurrence. Let $F(n,m,k)$ be the count over all functional graphs with $n$ nodes, $m$ special nodes, and $k$ leaves. Then, splitting on what the $n$ -th node is:

F(n,m,k) = {n'th is a leaf, pointing to a previous leaf}
         + {n'th is a leaf, pointing to a previous non-leaf}
         + {n'th is not a leaf}
         = F(n-1,m,k) * k  +  F(n-1,m-1,k-1) * (n-k-1)  +  ...

To be honest, I couldn't figure out the rest of the recurrence for the case where node $n$ is not a leaf. We have some good core ideas, but this recurrence is too complex to work with.

IdeaPrüfer sequences — what if it were a tree?No Solution

Problem Simplification

The cycles were confusing me, so I started wondering: could I solve this on a tree instead of a loopy functional graph? How many trees are there with $n$ nodes and $k$ leaves?

Ask for Help

After Googling a little, I found this is related to Prüfer sequences.

Definition.

A Prüfer sequence encodes a labeled tree on $n$ nodes as a sequence of $n-2$ numbers: repeatedly take the smallest-numbered leaf, remove it, and record its neighbor's label, until 2 nodes remain.

These sequences are a bijection: every sequence of $n-2$ numbers from $1..n$ corresponds to exactly one labeled tree, giving Cayley's formula $n^{n-2}$ for the number of labeled trees. For rooted trees the same procedure runs until only the root remains, giving sequences of length $n-1$ and $n^{n-1}$ rooted trees.

To count trees by their number of leaves, ask: can you read off the leaves from the Prüfer sequence?

Lemma.

In the rooted-tree encoding, the leaves of the tree are exactly the labels that do not appear in the Prüfer sequence — a leaf is never recorded as anyone's parent, while every internal node must be.

So let $T(n,k)$ be the number of rooted trees with $n$ nodes and $k$ leaves — equivalently, the number of sequences of length $n-1$ over $1..n$ in which exactly $k$ labels never appear.

Problem Transformation

Pretend we have $n-k$ boxes — the labels that do appear. We must assign each of the $n-1$ sequence slots to one of the boxes so that no box is empty. Partitioning items into non-empty groups is exactly the Stirling numbers of the second kind $S(n,k)$ — something I recognized from experience.

T(n,k) = \binom{n}{k} \cdot S(n-1,\, n-k) \cdot (n-k)!

(choose which $k$ labels are leaves; partition the $n-1$ slots into $n-k$ non-empty groups; assign the groups to actual labels.)

If we could compute the Stirling numbers, the tree version of the problem would follow by summing over the number of leaves $k$ , forcing all leaves to be special and choosing the remaining $m-k$ special nodes freely:

\text{Good}_{\text{trees}}(n,m) = \sum_{k=1}^{n} T(n,k)\binom{n-k}{m-k} = \sum_{k=1}^{n} \binom{n}{k} S(n-1, n-k)\,(n-k)!\,\binom{n-k}{m-k}

(Factorials up to $10^6$ and their modular inverses can be precomputed, making each binomial $O(1)$ .)

So the hard part is computing the Stirling numbers. There are two classic routes:

Algorithm— Stirling numbers via recursion

Consider item $n$ : either it is a singleton subset, or it joins one of the $k$ existing subsets:

S(n,k) = S(n-1,k-1) + k * S(n-1,k)

Correct, but $O(n^2)$ time and space — too slow here.

Algorithm— Stirling numbers via inclusion-exclusion

Number the $k$ boxes and assign each of the $n$ items a box: $k^n$ ways, but some boxes may be empty. Let $A_i$ be the assignments where box $i$ is empty; subtract the union via inclusion-exclusion (see the Aside below), then divide by $k!$ to unlabel the boxes:

S(n,k) = \frac{1}{k!} \sum_{j=0}^{k} (-1)^j \binom{k}{j} (k-j)^n

Defining $A_j := (-1)^j$ and $B_j := \binom{k}{j} j^n$ , both computable for all $j$ in $O(n)$ , the values $S(n,k)$ for all $k$ at once form a convolution $A * B$ — computable in $O(n \log n)$ with the Fast Fourier Transform (FFT).

A note on that last step: FFT is a relatively involved algorithm, and in another world I'd build it up here the way I do inclusion-exclusion below — but since we're about to move on from trees entirely, that would be a distraction. I did try to simplify $\text{Good}_{\text{trees}}$ to avoid the FFT, but the double sum doesn't separate: the inner index stays coupled to $k$ through the $(n-k-j)^n$ term, which is exactly the shape a convolution exists to handle.

Problem Generalization

With some work this extends to forests by adding a dummy root node $n+1$ . But I need functional graphs, not forests — good time to move on.

Observation.

We can use bijections from number sequences to trees (or forests, or graphs), and count sequences with certain properties instead of counting graphs directly.

Observation.

Inclusion-exclusion can turn these counting problems into explicit closed-form sums over one index $k = 1..n$ — which is $O(n)$ once factorials are precomputed.

AsideFormalizing Inclusion-Exclusion

A technique used briefly above, and heavily below, is inclusion-exclusion. I generally understand it, but it's worth formalizing.

Let $A$ and $B$ be two sets of outcomes — possibly overlapping. To count outcomes where at least one of them occurs:

Lemma.

$|A \cup B| = |A| + |B| - |A \cap B|$

Applying this repeatedly generalizes to more sets:

\begin{aligned} |A \cup B \cup C| &= |(A \cup B) \cup C| \\ &= |A \cup B| + |C| - |(A \cup B) \cap C| \\ &= |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \end{aligned}

and in general, for sets $A_1, \ldots, A_n$ :

\left| \bigcup_i A_i \right| = \sum_i |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots

The sign alternates with the number of sets intersected.

Why is this useful? In many problems, counting the intersection ( $A$ AND $B$ AND $C$ ) is far easier than counting the union ( $A$ OR $B$ OR $C$ ). If you can write a simple formula for the intersection of any subset of your sets, inclusion-exclusion hands you the union.

Work an Example

In the Stirling-number problem: let $A_i$ = assignments where box $i$ is empty. We want no box empty, i.e. $k^n - |A_1 \cup \cdots \cup A_k|$ . Any intersection of $j$ of these sets is trivial to count — it's just $(k-j)^n$ , assignments avoiding $j$ boxes — which yields the formula above.

Lesson

The trick to inclusion-exclusion is choosing the events so that describing any intersection of them is easy.

IdeaGeneralizing to functional graphs

Idea 2 was insightful but only handles trees. Functional graphs have cycles. It turns out the core approach — write the graph as a sequence and count sequences with the right properties — still works, together with inclusion-exclusion.

Instead of Prüfer sequences, work with what we've got directly: each node points to exactly one other node, so the sequence $(f_1, f_2, \ldots, f_n)$ — where $f_i$ is the node that $i$ points to, $f_i \neq i$ — uniquely determines the functional graph. There are $(n-1)^n$ such sequences.

Key Observation

A node is a leaf exactly when it never appears in the sequence $(f_1, \ldots, f_n)$ — the same trick as reading leaves off a Prüfer sequence, applied to the functional graph's own pointer sequence. So we can do inclusion-exclusion directly on "node $i$ never appears."

By symmetry, first choose the $m$ special nodes: $\binom{n}{m}$ ways; say they are nodes $1..m$ . A selection fails on leaves if some non-special node is a leaf. Let $A_i$ (for $i > m$ ) be the set of sequences where node $i$ is a leaf.

For a fixed set of $k$ forced leaves, count the sequences: each forced leaf must point somewhere (but not to itself or another forced leaf, which must stay leaves) — $(n-k)$ choices each — and each of the other $n-k$ nodes must avoid itself and all $k$ leaves — $(n-1-k)$ choices each. So by inclusion-exclusion, the number of sequences with no bad leaves is:

\sum_{k=0}^{n-m} (-1)^k \binom{n-m}{k} (n-k)^k (n-1-k)^{n-k}

and the candidate answer is $\binom{n}{m}$ times that. We're making a ton of progress — but this is still wrong: it ignores the pure cycles. A component that is a bare cycle with no special node on it is unreachable, and nothing above accounts for that.

Let's tackle that next.

IdeaPure cycles and derangements

Draw from Experience

If the graph consisted of only pure cycles, it would look exactly like a permutation — any permutation decomposes into disjoint cycles. Cycle-counting on permutations is the territory of the (unsigned) Stirling numbers of the first kind. Useful, or a distraction...

Since self-loops are forbidden, we need permutations with no fixed points — these are called derangements. (The first-kind Stirling numbers aren't directly applicable.)

Definition.

From here on, derangement means a permutation with no fixed points — equivalently, a functional graph consisting only of pure cycles of length $\geq 2$ . The equivalence: in a permutation every node has out-degree 1 and in-degree 1, so the graph is exactly a disjoint union of cycles, and "no fixed points" is precisely "no self-loops."

It turns out derangements are counted by — you guessed it — inclusion-exclusion. Let $A_i$ be the permutations where element $i$ is a fixed point. Then:

D(n) = n! - \left|\bigcup_i A_i\right| = \sum_{j=0}^{n} (-1)^j \binom{n}{j} (n-j)! = n! \sum_{j=0}^{n} \frac{(-1)^j}{j!}

(the middle step expands $\binom{n}{j}(n-j)! = n!/j!$ ). This is computable in $O(n)$ — or all values $D(0..n)$ in one $O(n)$ sweep.

Ask for Help

Side note: that last sum is the power series of $e^x$ at $x = -1$ , so $D(n) \approx n!/e$ — in fact $D(n) = \text{round}(n!/e)$ exactly, for all $n \geq 1$ . (We work modulo $998244353$ , so we use the sum, not the rounding trick.)

Observation.

Using inclusion-exclusion, all derangement counts $D(0..n)$ can be precomputed in $O(n)$ total time.

This counts the pure-cycle graphs. But our problem also chooses $m$ special nodes, and demands every cycle contain one. So the next question is how to count derangement–selection pairs where no cycle is missed — still on pure cycles only, which remains a useful stepping stone before combining everything.

IdeaCounting good selections on pure cycles

Idea 4 counts pure-cycle graphs; now, on a graph of only pure cycles (a derangement), count selections of $m$ special nodes such that every cycle contains at least one of them. This is the part that stumped me.

Ask for Help

I was stuck here for a while and looked at the solution — so this section is a reverse-engineering of the logic. I completely missed the key observation, and I think you'll find it fun to reconstruct.

Given how far we've come, we want inclusion-exclusion. But on what events?

My first attempt: let $A_i$ be the derangement–selection pairs where node $i$ is trapped in a bad cycle (one containing no special node). Then the answer would be $D(n) - |A_1 \cup \cdots \cup A_n|$ ... and this is where I got stuck. I could not write down clean formulas for the intersections $|A_i \cap A_j \cap \cdots|$ .

Observation.

Inclusion-exclusion only works when you have a clean way to count the intersections. If the intersections are gnarly, you've chosen the wrong events.

Key Question

If we want to penalize "bad cycles," what should the events be?

Key Observation

The cycles ARE the events. Fix the $m$ special nodes. For each possible cycle $C$ containing no special node (a bad candidate), let $X_C$ be the set of derangements in which $C$ appears as one of the cycles. There may be a gazillion candidate cycles, but the answer is simply $D(n) - |X_{C_1} \cup X_{C_2} \cup \cdots|$ over all bad candidates — and these intersections are easy: once you decide that specific cycles appear, all their nodes' edges are fixed, and the remaining nodes just form a derangement among themselves.

Concretely: an intersection of $c$ disjoint bad cycles covering $j$ nodes fixes those $j$ nodes entirely, and the other $n-j$ nodes can be deranged freely among themselves: $D(n-j)$ ways. First choose which $j$ non-special nodes sit in the bad cycles — $\binom{n-m}{j}$ ways — then let $W_{j,c}$ count the ways to arrange those $j$ nodes into exactly $c$ cycles (each of length $\geq 2$ ). Inclusion-exclusion gives:

\text{Good}_{\text{cycles}}(n,m) = \binom{n}{m} \sum_{j=0}^{n-m} \sum_{c=0}^{j} (-1)^{c} \binom{n-m}{j} W_{j,c}\, D(n-j)

Pull everything independent of $c$ out of the inner sum:

= \binom{n}{m} \sum_{j=0}^{n-m} \binom{n-m}{j} D(n-j) \left[ \sum_{c=0}^{j} (-1)^{c} W_{j,c} \right]

If we could kill that inner sum, we'd have a single $O(n)$ loop. First, $W_{j,c}$ satisfies a recursion (good ol' fashioned recursion — no inclusion-exclusion needed): let $\ell \geq 2$ be the length of the cycle containing the $j$ -th node — choose its $\ell - 1$ companions and arrange the cycle:

W_{j,c} = \sum_{\ell=2}^{j} \binom{j-1}{\ell-1} (\ell-1)!\; W_{j-\ell,\,c-1} = (j-1)! \sum_{r=0}^{j-2} \frac{W_{r,\,c-1}}{r!}

Not obviously simpler — but substitute it into the alternating sum. Writing $\Phi(j) := \sum_{c} (-1)^c W_{j,c}$ :

\Phi(j) = \sum_{c} (-1)^{c} (j-1)! \sum_{r=0}^{j-2} \frac{W_{r,c-1}}{r!} = -(j-1)! \sum_{r=0}^{j-2} \frac{\Phi(r)}{r!}

Key Observation

$\Phi(j) = \sum_{c=0}^{j} (-1)^c W_{j,c} = 1 - j$ for all $j \geq 0$ .

Proof.

Induction on $j$ . Base cases: $\Phi(0) = W_{0,0} = 1 = 1-0$ (the empty arrangement), and $\Phi(1) = 0 = 1-1$ (one node can't form a cycle of length $\geq 2$ ). For $j \geq 2$ , assume $\Phi(r) = 1-r$ for all $r < j$ . The summand telescopes: for $r \geq 1$ ,

\frac{1-r}{r!} = \frac{1}{r!} - \frac{r}{r!} = \frac{1}{r!} - \frac{1}{(r-1)!}

\sum_{r=0}^{j-2} \frac{1-r}{r!} = 1 + \left(\frac{1}{(j-2)!} - \frac{1}{0!}\right) = \frac{1}{(j-2)!}

and therefore

\Phi(j) = -(j-1)! \cdot \frac{1}{(j-2)!} = -(j-1) = 1-j.

∎

So the pure-cycle answer collapses to a single sum:

\text{Good}_{\text{cycles}}(n,m) = \binom{n}{m} \sum_{j=0}^{n-m} \binom{n-m}{j}\, D(n-j)\, (1-j)

with derangements and factorials precomputed in $O(n)$ . Notice again: $n$ and $m$ are treated as fixed constants; we only sum over $j$ .

In Idea 3 we got the core idea for components with leaves. Here we got the core idea for cycles. Can we put it all together?

IdeaPutting it all togetherAC

The final solution combines Ideas 3 and 5 into one inclusion-exclusion over all the bad events at once.

Fix $n$ and $m$ ; choose the $m$ special nodes ( $\binom{n}{m}$ ways, WLOG nodes $1..m$ ), and represent each graph as its pointer sequence $(f_1, \ldots, f_n)$ . The bad events:

$A_i$ for each non-special node $i$ : node $i$ is a leaf (appears nowhere in the sequence);
$X_C$ for each special-free cycle $C$ : the nodes of $C$ form exactly that cycle, and nothing outside points into it (a pure bad cycle).

A selection is bad iff at least one of these occurs, so we subtract $\left| \bigcup A_i \cup \bigcup X_C \right|$ from $(n-1)^n$ via inclusion-exclusion. Consider an intersection with $k$ leaf-events and $c$ cycle-events covering $j$ nodes (sign $(-1)^{k+c}$ ):

choose the $j$ nodes for the bad cycles ( $\binom{n-m}{j}$ ways), then form the cycles ( $W_{j,c}$ ways) — their edges are now fixed;
each of the $k$ forced leaves points anywhere except itself, the other leaves, and the cycle nodes: $(n-j-k)$ choices;
each of the remaining $n-j-k$ free nodes avoids itself, the leaves, and the cycle nodes: $(n-1-j-k)$ choices.

\text{Good}(n,m) = \binom{n}{m} \sum_{j=0}^{n-m} \binom{n-m}{j} \sum_{k=0}^{n-m-j} (-1)^k \binom{n-m-j}{k} (n-1-j-k)^{n-j-k} (n-j-k)^k \sum_{c=0}^{j} (-1)^{c} W_{j,c}

Now simplify, in three moves:

Replace the inner $c$ -sum with $1-j$ (Key Observation 6).
Substitute $a := j+k$ and regroup — the summand depends on $j,k$ only through $a$ and the leftover $(1-j)$ , and the binomials merge as $\binom{n-m}{j}\binom{n-m-j}{k} = \binom{n-m}{a}\binom{a}{k}$ .
Pull the $a$ -only factors out of the inner sum.

\text{Good}(n,m) = \binom{n}{m} \sum_{a=0}^{n-m} \binom{n-m}{a} (n-1-a)^{n-a} \sum_{k=0}^{a} (-1)^k \binom{a}{k} (n-a)^k \left(1-(a-k)\right)

Split the inner sum using $1-(a-k) = 1 - a + k$ into a plain part and an $(a-k)$ -weighted part. Both collapse:

Key Observation

By the Binomial Theorem $(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k$ with $x = 1$ , $y = -(n-a)$ :

\sum_{k=0}^{a} (-1)^k \binom{a}{k} (n-a)^k = (1 + a - n)^a

and by differentiating the Binomial Theorem in $x$ — giving $n(x+y)^{n-1} = \sum_{k} \binom{n}{k}(n-k)\,x^{n-k-1} y^k$ — the weighted sum collapses too:

\sum_{k=0}^{a} (-1)^k \binom{a}{k} (n-a)^k (a-k) = a\,(1+a-n)^{a-1}

Draw from Experience

The binomial theorem is standard; the derivative trick — differentiate a known identity to collapse an index-weighted sum — is one I'd seen before in generating-function problems, and [Write It Out] is what surfaced it here.

Substituting both back:

\text{Good}(n,m) = \binom{n}{m} \sum_{a=0}^{n-m} \binom{n-m}{a} (n-1-a)^{n-a} \left[ (1+a-n)^a - a(1+a-n)^{a-1} \right]

Factor the bracket: $(1+a-n)^{a-1}\left[(1+a-n) - a\right] = (1-n)(1+a-n)^{a-1}$ , and since $(1+a-n) = -(n-1-a)$ , we get $(1+a-n)^{a-1} = (-1)^{a-1}(n-1-a)^{a-1}$ , which merges with the $(n-1-a)^{n-a}$ into a single power:

\boxed{\;\text{Good}(n,m) = \binom{n}{m}\,(n-1) \sum_{a=0}^{n-m} (-1)^{a} \binom{n-m}{a}\, (n-1-a)^{n-1}\;}

After the inclusion-exclusion miraculously telescopes and simplifies, we sum over a single index $a$ , treating $n$ and $m$ as constants, using precomputed factorials and fast exponentiation for $(n-1-a)^{n-1}$ . Total: $O(n \log n)$ (the $\log$ from the modular exponentiations).

Review

The number of good (graph, selection) pairs, modulo $998244353$ , is

\text{Good}(n,m) = \binom{n}{m}\,(n-1) \sum_{a=0}^{n-m} (-1)^{a} \binom{n-m}{a}\, (n-1-a)^{n-1}

computable in $O(n \log n)$ . The path there, in key observations:

Structure. A functional graph is cycles with trees attached. A selection is good iff every leaf is special and every pure cycle contains a special node. [1][2][3]
Sequences, not graphs. Encode each graph as its pointer sequence $(f_1, \ldots, f_n)$ ; a node is a leaf iff its label never appears in the sequence. [4]
Inclusion-exclusion needs countable intersections. Choose the events so that intersecting any subset of them is easy to count.
The cycles are the events. One event per special-free candidate cycle ("this exact cycle appears, untouched") freezes its nodes and leaves a clean sub-problem — intersections become trivial, even combined with the leaf events. [5]
The master sum. Intersecting $k$ leaf-events with $c$ bad cycles covering $j$ nodes — where $W_{j,c}$ counts the ways to arrange $j$ chosen nodes into exactly $c$ cycles of length $\geq 2$ — gives:

\binom{n}{m} \sum_{j} \binom{n-m}{j} \sum_{k} (-1)^k \binom{n-m-j}{k} (n-1-j-k)^{n-j-k} (n-j-k)^k \sum_{c} (-1)^{c} W_{j,c}

The alternating cycle-sum collapses: $\sum_c (-1)^c W_{j,c} = 1-j$ , by a telescoping induction. [6]
The binomial theorem — and its derivative — kill the remaining inner sum, leaving the single-sum formula above. [7]

Pseudocode:

MAXN = 10**6 + 5
PRIME = 998244353
 
# O(MAXN) precomputation
fact = [1] * MAXN
for i in range(1, MAXN):
    fact[i] = fact[i-1] * i % PRIME
invfact = [modinv(f) for f in fact]   # modinv via pow(f, PRIME-2, PRIME)
 
def choose(n, k):
    if k < 0 or k > n: return 0
    return fact[n] * invfact[k] % PRIME * invfact[n-k] % PRIME
 
def solve(n, m):
    ans = 0
    for a in range(0, n - m + 1):
        term = choose(n - m, a) * pow(n - 1 - a, n - 1, PRIME) % PRIME
        ans = (ans - term if a % 2 else ans + term) % PRIME
    ans = ans * (n - 1) % PRIME
    ans = ans * choose(n, m) % PRIME
    return ans

References

Learning points. In the end this problem was an exercise in inclusion-exclusion, and in being very careful about how you count and decompose the sets.

I got quickly to "look at the leaves and the pure cycles," and tried solving them separately — then got completely stumped on the pure cycles. Part of it was that I kept looking for a recursion on the $m$ -th or $n$ -th node, but the recursion was tricky to get right, if it exists at all. Just as with Stirling numbers of the second kind, some counting problems admit both a recursion and an inclusion-exclusion formula — and they have very different computational profiles.

Inclusion-exclusion works when you have an easy time intersecting interesting configurations $|A \cap B \cap C|$ but a hard time with the union $|A \cup B \cup C|$ . Overlapping, conflicting configurations are fine — as long as every subset of events with a known "size" $j$ has a countable intersection, the machinery $(-1)^j |\cdots|$ does the rest.

The hardest part for me was recognizing how to run inclusion-exclusion on the pure cycles. I kept choosing "number of nodes trapped in bad cycles" as the quantity to sum over, and no formula worked — there was no clean way to AND together "these particular nodes are in bad cycles." The aha came from making the cycles themselves the events: once a cycle is required to appear, its nodes are frozen and everything else derangles freely, so intersections become easy — even when combined with the leaf events. The resulting sums looked terrifying, then telescoped and collapsed.

I don't think it will always be that clean — but sometimes you just have to [Write It Out], and watch the formula simplify. Notably, $n$ and $m$ factored out as constants throughout: we never needed the answer for all $(n,m)$ , just one final sum over a single index.

I feel I learned a lot about inclusion-exclusion from this problem — and about how seemingly intractable counting problems fall apart once you pick the right events.

Topics: inclusion-exclusion · permutations, derangements, cycle notation · combinatorics, binomial coefficients · recursion & induction · modular arithmetic · fast exponentiation

Related: Stirling numbers (first & second kind) · Prüfer sequences & Cayley's formula · counting labeled trees by leaves