Note on A000081
---------------

A000081 is number of rooted trees with n nodes.

Claim: This is also the number of ways of arranging
n-1 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