Trees with Labeled Nodes that form Permutation of Positive Integers

Paul D. Hanna pauldhanna at juno.com
Wed Nov 15 05:04:51 CET 2006


Seqfans, 
    Could someone compute the initial terms of the following. 
I do not believe that it is in the OEIS (?). 
  
Number of labelled nodes in generation n of a rooted tree 
where a node with label k has k child nodes such that 
the label of each child node is the least unused label in 
the path from the root to that child node, 
and where root is labeled '1'. 
  
Thus every distinct path in the tree eventually forms 
a permutation of the positive integers. 
 
The wording needs to be made more precise and concise. 
 
Here are the initial nodes of the tree for generations 0..4: 
Gen 0: [1];
Gen 1: (1)->[2];
Gen 2: (2)->[3,4];
Gen 3: (3)->[4,5,6], (4)->[3,5,6,7];
Gen 4: (4)->[5,6,7,8], (5)->[4,6,7,8,9], (6)->[4,5,7,8,9,10], 
(3)->[5,6,7], (5)->[3,6,7,8,9], (6)->[3,5,7,8,9,10], 
(7)->[3,5,6,8,9,10,11]; ...
 
Thus, the number of nodes in generation n begins:
[1, 1, 2, 7, 36, 248, ...]
 
The maximum node in generation n begins:
[1, 2, 4, 7, 11, ...]
 
Would appreciate it if someone could compute more terms.
Thanks,
      Paul






More information about the SeqFan mailing list