Friday, 30 May 2008

co.combinatorics - Describe a tree by junctions

I have n sectors, enumerated 0 to n-1 counterclockwise. The boundaries between these sectors are infinite branches (n of them).



These branches meet at certain points (junctions). Each junction is adjacent to a subset of the sectors (at least 3 of them).



By specifying what sectors my junctions are adjacent to, I can completely recover the tree.
This seems like something known, but I would like a reference to it.



The number of trees with n branches is given by
http://www.oeis.org/A001003
and this is quite easy to prove.



Furthermore, if I order the sectors in the description of the junctions, I can make this representation unique.



Example:
(0,1,2,3,4,5) represents the tree with only one vertex, and 6 branches connected to this junction.

No comments:

Post a Comment