Note on A000081

A000081 is number of rooted trees with n nodes.
Claim: This is also the number of ways of arranging
n1 nonoverlapping circles.
Proof: The bijection is established by induction on n.
First some examples: The root of the tree is indicated by X,
the other nodes by small circles o.
n=2:
the unique tree with 2 nodes: arrangements of 1 circle:
o
 O
X
n=3:
trees with 3 nodes: arrangements of 2 circles:
o

o 2 concentric circles

X
o o
\ / O O
X
trees with 4 nodes: arrangements of 3 circle:
o

o

o 3 concentric circles

X
o
\
o o O + 2 concentric circles
\/
X
o o
\ /
o big circle containing O O

X
o o o
\/ O O O
X
In general: we build up the isomorphism inductively:
Rooted tree Arrangement of circles
If
a <> A
and
b <> B
then
a
 <> A inside a circle
X
and
two rooted trees a and b sharing a common root X
(for technical reasons X is shown BETWEEN the two trees):
....... .......
.. .. .. ..
.. .. .. ..
. . . .
. tree . tree .
. a X b . <> A next to B
. . .
. . . .
.. .. .. ..
.. .. .. ..
....... .......
Exercise: do the mapping for the 9 rooted trees with 5 nodes.
Neil Sloane, Oct 29 2004