login
Number of labeled nodes in generation n of a rooted tree where a node with label k has k child nodes with distinct labels, such that each child node is assigned the least unused label in the path that leads back to the root node with label '1'.
1

%I #8 Mar 31 2012 09:15:14

%S 1,1,2,7,36,248,2157,22761,283220,4068411,66367834,1213504295,

%T 24606397802

%N Number of labeled nodes in generation n of a rooted tree where a node with label k has k child nodes with distinct labels, such that each child node is assigned the least unused label in the path that leads back to the root node with label '1'.

%C The minimum label in generation n is n+1 and the maximum label is n*(n+1)/2 + 1.

%C Compare to trees A029768, A007889, which seem somewhat similar; A029768 has the additional constraint that the labels must be increasing.

%H Alec Mihailovs, <a href="http://www.mapleprimes.com/blog/alec/a125033">A125033: Maple Program</a> (non-recursive, uses little memory); Mapleprimes, Nov 19 2006.

%e Labels for the initial nodes of the tree for generations 0..4:

%e gen 0: [1];

%e gen 1: (1)->[2];

%e gen 2: (2)->[3,4];

%e gen 3: (3)->[4,5,6], (4)->[3,5,6,7];

%e gen 4: (4)->[5,6,7,8], (5)->[4,6,7,8,9], (6)->[4,5,7,8,9,10],

%e (3)->[5,6,7], (5)->[3,6,7,8,9], (6)->[3,5,7,8,9,10],

%e (7)->[3,5,6,8,9,10,11];

%p gen := proc(parents,maxgen,ocounts,lvl)

%p local thislbl,lbl,childlbl,counts,npar;

%p counts := ocounts;

%p counts[lvl] := counts[lvl]+1;

%p if nops(parents) < maxgen then

%p thislbl := op(-1,parents);

%p childlbl := 1;

%p for lbl from 1 to thislbl do

%p while ( childlbl in parents ) or ( childlbl = thislbl ) do

%p childlbl := childlbl+1;

%p od;

%p npar := [op(parents),childlbl];

%p if nops(counts) < lvl+1 then

%p counts := [op(counts),0];

%p fi;

%p counts := gen(npar,maxgen,counts,lvl+1);

%p childlbl := childlbl+1;

%p od;

%p fi;

%p if lvl <= maxgen -4 then

%p print(counts);

%p fi;

%p RETURN(counts);

%p end:

%p maxgen := 8;

%p parents := [1,2];

%p n := [1,0];

%p gen(parents,maxgen,n,2);

%p print(%) ; # _R. J. Mathar_, Nov 17 2006)

%p The following Maple10 code is from Alec Mihailovs: # (start)

%p f:=proc(n::integer[4],A::Array(datatype=integer[4]),

%p B::Array(datatype=integer[4]))::integer[4]; local c::integer[4],

%p i::integer[4],len::integer[4],m::integer[4]; c,len,m:=0,3,3;

%p while len>1 do if len=n then c:=c+1;m:=A[len];B[m]:=0;len:=len-1;

%p B[A[len]]:=B[A[len]]+1 elif B[A[len]]<=A[len] then for i from m+1

%p do if B[i]=0 then break fi od; len:=len+1;A[len]:=i;B[i]:=1;m:=2

%p else m:=A[len];B[m]:=0;len:=len-1;B[A[len]]:=B[A[len]]+1 fi od; c end:

%p cf:=Compiler:-Compile(f):

%p F:=proc(n::posint) local A,B;

%p if n<3 then 1 elif n=3 then 2 else

%p A:=Array([$1..3,0$(n-3)],datatype=integer[4]);

%p B:=Array([1$3,0$((n-2)*(n+1)/2)],datatype=integer[4]);

%p cf(n,A,B) fi end:

%p seq(F(n),n=1..12); # (end)

%K nonn

%O 0,3

%A _Paul D. Hanna_ and _R. J. Mathar_, Nov 17 2006

%E Terms a(6)-a(10) from _R. J. Mathar_, Nov 17 2006

%E a(11) and a(12) from Alec Mihailovs (alec(AT)mihailovs.com), Nov 19 2006