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> Return-Path: <seqfan-owner at ext.jussieu.fr>
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> 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, ...]
pdh>  
pdh> Would appreciate it if someone could compute more terms.
pdh> Thanks,
pdh>       Paul

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

The maximum node label is trivially A000124 because the maximum node will be
generated from the child with itself the highest label, and this adds 'n' to
the maximum label for each new generation. This produces the arithmetic sum
sequence that is shown above as the last number in each row.

For those who have some spare computer cycles and Maple: below is a program
that runs recursively ("memory friendly") through the entire tree up to 
some maximum generation 'maxgen' (to be set/edited in the fourth but last line
below, maxgen=10 equivalent to Gen up to 9 above). It prints a film of
progresses made to count the nodes found so far at all levels, and should show
all numbers in the list monotonically increasing slowly towards
[1, 1, 2, 7, 36, 248, 2157, 22761, 283220, 4068411, 66367834, ...]
                                                    ^^^ 66367834 is Gen 10
I can also provide my older (but non-recursive, memory-limited) C++ version.

Maple V:

gen := proc(parents,maxgen,ocounts,lvl)
	local thislbl,lbl,childlbl,counts,npar ;
	counts := ocounts ;
	counts[lvl] := counts[lvl]+1 ;
	if nops(parents) < maxgen then
		thislbl := op(-1,parents) ;
		childlbl := 1 ;
		for lbl from 1 to thislbl do
			while ( childlbl in parents ) or ( childlbl = thislbl ) do
				childlbl := childlbl+1 ;
			od ;
			npar := [op(parents),childlbl] ;
			# this would generate a full list of all paths:
			# print("route",npar) ;
			if nops(counts) < lvl+1 then
				counts := [op(counts),0] ;
			fi ;
			counts := gen(npar,maxgen,counts,lvl+1) ;
			childlbl := childlbl+1 ;
		od ;
	fi ;
	# this produces a snapshot of the counts accumulated so far:
	# if the current node creation level is not too high, print it...
	if lvl <= maxgen -3 then
		print(counts) ;
	fi ;
	RETURN(counts) ;
end:

# Edit the maximum number below...total run time probably grows exponentially
# with the number chosen here.
maxgen := 8 ;
parents := [1,2] ;
n := [1,0] ;
gen(parents,maxgen,n,2) ;
print(%) ;