combinatoricsgraph theorytrees
A rooted forest on $\{1,…,n\}$ is a forest together with a choice of a root in each component tree.
Let $F(n,k)$ be the set of all rooted forests that consist
of $k$ rooted trees.
Thus $F(n,1)$ is the set of all rooted trees.
Question:
Enumerate all elements of the set $F(3,1)$.
I think it should be only 3 as follows:
But the answer says 9.
Can someone enumerate those for me?
Here's another proof, I believe due to Jim Pitman.
A rooted forest is a disjoint union of rooted trees, which we will think of as a digraph with edges always directed toward the roots. Given a rooted forest $F$ on $n$ vertices with $k$ components, we would like to add an edge while still having a forest. To do this, choose any vertex $x$ and any of the $k-1$ roots $y$ not in the same component as $x$ and add the edge $y \rightarrow x$. There are thus $n(k-1)$ ways of doing this, and the resulting forest now has $k-1$ components. If we start from forest with $n$ isolated vertices, we see that we can add $n-1$ edges in
$$n(n-1)\cdot n(n-2) \cdot \ldots \cdot n(1) = (n-1)! \cdot n^{n-1}$$ ways. In this expression each tree has been counted $(n-1)!$ ways since the order in which we added edges does not matter, so dividing this out gives the desired formula.
Graphs usually have many forests as subgraphs. How to make them? Delete some vertices and/or edges: if there's no cycles, it's a forest.
For example, this disconnected graph
has the forests
(which happens to have a spanning tree in each connected component) and
as subgraphs. [In fact, the two subgraphs above happen to be spanning forests (in the sense that the forest and the original graph have the same vertex set). However, it can also be useful to define "spanning forest" to mean having a spanning tree in each connected component.]
It contains non-spanning forests, such as
and it even contains forests without any edges, such as
and
Best Answer
A rooted tree is a labeled tree where one of the vertices is chosen to be the root. You have listed all labeled trees, but have not chosen the root for each. There are three choices for the root for each of the three labeled trees, so there are $9$ rooted trees in $F(3,1)$. They look like this: