Strange Counting Added

Here are some common graph counting routines. Since my polynomial skills are zero, I won't optimize the formulas. If you find any issues with the formulas or know how to optimize them, please tell me directly.

Undirected Graph Counting

How many undirected graphs with $n$ nodes are there?

To improve the reading experience of a blog that nobody would read anyway, let's start with something simple.

Consider that each point can connect at most one edge to each remaining point, for a total of $n-1$ edges,
Since it's an undirected graph, each edge is counted once by each of its two endpoints,
so an undirected graph can have at most $\frac{n(n-1)}{2}$ edges.

Because each edge independently has two possibilities: connected or not,
there are a total of $2^{\frac{n(n-1)}{2}}$ ways to connect edges.

Prufer Sequence

How many labeled unrooted trees are there?

Cayley's Formula

Cayley's formula states that there are $n^{n-2}$ unrooted trees with $n$ nodes.

The Prufer sequence demonstrates a bijection between a sequence and a labeled unrooted tree,
that is, the number of sequences satisfying a certain rule is the number of labeled unrooted trees.

The Prufer sequence was designed to prove Cayley's formula.

Construction

Try to prove the bijection between sequences and labeled unrooted trees, which can help us understand this formula.
Of course, we can also directly memorize such a simple formula.

Given a tree, how do we construct its Prufer sequence?

According to the definition of the Prufer sequence, each time remove the leaf with the smallest label and record the edge it connects to, until two nodes remain.

Given a sequence, how do we construct a tree using the Prufer method?

Observing the construction method, we get some information:

• Among the remaining two points, one must be node $n$.
• The degree of node $i$ is the number of times it appears in the sequence plus 1.
• From the previous point, nodes not appearing in the sequence are leaf nodes.

After we get all leaf nodes, we can add points in the same way as removing points.
The first value in the sequence is the edge connected to the smallest leaf node, and so on.
Maintain a min-heap; if a new leaf node is generated, add it to the heap.
Finally, two points remain, connect them directly.

It can be seen that a tree can construct a unique sequence, and a sequence can construct a unique tree.

Binary Tree Counting

How many unlabeled binary trees with N points are there? (Binary trees are rooted by default, and symmetry is not considered the same)

Recursive Method

For a binary tree with $N$ nodes, we can enumerate the size of one subtree, and then the size of the other subtree is determined.
Let $f_i$ denote the number of ways to construct a subtree with $i$ nodes. $$f_i=\sum_{j=0}^{i-1}{f_j \times f_{i-1-j}}$$

Catalan Numbers

We find that the above formula is the recurrence for Catalan numbers, so we can also directly use the Catalan number formula to solve it.

We can consider the bijection between valid bracket sequences and binary trees.
Consider the origin of the Catalan recurrence: each time a bracket is added, enumerate the number of valid bracket sequences inside the bracket and to the right of the bracket.
Extended to binary trees, each time match the first left bracket; the inside of the bracket is the left subtree, and the right of the bracket is the right subtree.

Undirected Connected Graph Counting

How many labeled undirected connected graphs are there?

Consider an inclusion-exclusion, subtracting the disconnected connection ways from all connection ways.

We fix a point and enumerate the size of the connected component it belongs to.
Let the size of the connected component be $j$, combine to choose the $j$ points and multiply by the number of connected graphs on $j$ points $f_j$,
and the outside of the connected component can be connected arbitrarily, which is $2^{\frac{(n-j)(n-j-1)}{2}}$.

$$f_i= 2^{\frac{n(n-1)}{2}} -\sum_{j=1}^{i-1}{ C_{i-1}^{j-1} \times f_j \times 2^{\frac{(i-j)(i-j-1)}{2}} }$$

Thus we can compute recursively in $O(n^2)$.

Bipartite Graph Counting

How many labeled bipartite graphs with $n$ points and $m$ connected components are there?

Let's change our approach and try to find the number of colored bipartite graphs $S$ (not necessarily connected).
Enumerate the set of points on one side, then connect edges arbitrarily between the two sides.
$$S_n= \sum_{i=0}^{n}{ C_{n}^{i} \times 2^{i(n-i)} }$$

At the same time, let $f_{i,j}$ be the number of bipartite graphs with $i$ points and $j$ connected components.
Using a method similar to undirected connected graph counting, fix a point and enumerate the size of the connected component to get:
$$f_{i,j}= \sum_{k=1}^{i-j+1}{ C_{i-k}^{k-1} \times f_{k,1} \times f_{i-k,j-1} }$$

We see that we cannot find $f_{i,1}$ this way. Don't be discouraged; let's try to establish a relationship between $S$ and $f$.
For each connected component, we have $2$ coloring schemes, so for $i$ connected components, there are $2^{i}$ coloring schemes.
$$S_n=\sum_{i=1}^{n}{ f_{n,i} \times 2^{i} }$$

There should be a table here.

Our $S_n$ is a parameterized sum over a column of $f$, so when we have the values in this column except $f_{n,1}$, we can get $f_{n,1}$.
All $f_{i,i}$ are obvious,
and the recurrence for $f_{i,j}$ only needs values with $i'<i$ and $j'<j$, which can be obtained by the above method.

Specifically, we enumerate the first dimension in increasing order of $i$, and the second dimension in decreasing order of $j$.
When $j>1$, we directly recurse; when $j=1$, we obtain it by subtracting from $S_n$.

Base Cycle Tree Counting

How many labeled base cycle trees are there?

This problem is actually simpler than the previous one QwQ.

If we have a forest, we just need to arrange all trees in a cycle.
Let $f_{i,j}$ be the number of ways to have $i$ points and $j$ trees.

Each time choose $k$ points as one tree to add to the answer: $$f_{i,j}= \sum_{k=1}^{i-j+1}{ C_{i}^{k} \times f_{k,1} \times f_{i-k,j-1} }$$ $f_{k,1}$ is solved using Cayley's formula.

Finally, multiply by the cyclic permutation: $$\sum_{i=3}^{n}{ f_{n,i} \times \frac{(i-1)!}{2} }$$

An Expected Value Problem

Why does this appear here? Probably because it was covered in class, so I put it here.

On the number line, there are $2n$ positions. Fill each position with a bracket to make the entire sequence a valid bracket sequence. What is the expected distance of a pair of brackets?