Trees with Labeled Nodes that form Permutation of Positive Integers

[Richard Mathar]

pdh> From seqfan-owner at ext.jussieu.fr  Wed Nov 15 05:08:51 2006
pdh> To: seqfan at ext.jussieu.fr
pdh> Date: Tue, 14 Nov 2006 23:04:51 -0500
pdh> Subject: Trees with Labeled Nodes that form Permutation of Positive Integers
pdh> From: "Paul D. Hanna" <pauldhanna at juno.com>
pdh> ...
pdh> Number of labelled nodes in generation n of a rooted tree 
pdh> where a node with label k has k child nodes such that 
pdh> the label of each child node is the least unused label in 
pdh> the path from the root to that child node, 
pdh> and where root is labeled '1'. 
pdh>   
pdh> Thus every distinct path in the tree eventually forms 
pdh> a permutation of the positive integers. 
pdh>  
pdh> The wording needs to be made more precise and concise. 
pdh>  
pdh> Here are the initial nodes of the tree for generations 0..4: 
pdh> Gen 0: [1];
pdh> Gen 1: (1)->[2];
pdh> Gen 2: (2)->[3,4];
pdh> Gen 3: (3)->[4,5,6], (4)->[3,5,6,7];
pdh> Gen 4: (4)->[5,6,7,8], (5)->[4,6,7,8,9], (6)->[4,5,7,8,9,10], 
pdh> (3)->[5,6,7], (5)->[3,6,7,8,9], (6)->[3,5,7,8,9,10], 
pdh> (7)->[3,5,6,8,9,10,11]; ...
pdh>  
pdh> Thus, the number of nodes in generation n begins:
pdh> [1, 1, 2, 7, 36, 248, ...]
pdh>  
pdh> The maximum node in generation n begins:
pdh> [1, 2, 4, 7, 11, ...]

My count of node numbers and maximum nodes is
Gen 0 1 1
Gen 1 1 2
Gen 2 2 4
Gen 3 7 7
Gen 4 36 11
Gen 5 248 16
Gen 6 2157 22
Gen 7 22761 29
Gen 8 283220 37
Gen 9 4068411 46

This list is limited by the simplicity of my program which keeps all the
trees in memory at the same time and runs into allocation problems if the
tenth generations are attempted.