cp's OEIS Frontend

A125033 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'.

%I A125033 #8 Mar 31 2012 09:15:14
%S A125033 1,1,2,7,36,248,2157,22761,283220,4068411,66367834,1213504295,
%T A125033 24606397802
%N A125033 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 A125033 The minimum label in generation n is n+1 and the maximum label is n*(n+1)/2 + 1.
%C A125033 Compare to trees A029768, A007889, which seem somewhat similar; A029768 has the additional constraint that the labels must be increasing.
%H A125033 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 A125033 Labels for the initial nodes of the tree for generations 0..4:
%e A125033 gen 0: [1];
%e A125033 gen 1: (1)->[2];
%e A125033 gen 2: (2)->[3,4];
%e A125033 gen 3: (3)->[4,5,6], (4)->[3,5,6,7];
%e A125033 gen 4: (4)->[5,6,7,8], (5)->[4,6,7,8,9], (6)->[4,5,7,8,9,10],
%e A125033 (3)->[5,6,7], (5)->[3,6,7,8,9], (6)->[3,5,7,8,9,10],
%e A125033 (7)->[3,5,6,8,9,10,11];
%p A125033 gen := proc(parents,maxgen,ocounts,lvl)
%p A125033 local thislbl,lbl,childlbl,counts,npar;
%p A125033 counts := ocounts;
%p A125033 counts[lvl] := counts[lvl]+1;
%p A125033 if nops(parents) < maxgen then
%p A125033 thislbl := op(-1,parents);
%p A125033 childlbl := 1;
%p A125033 for lbl from 1 to thislbl do
%p A125033 while ( childlbl in parents ) or ( childlbl = thislbl ) do
%p A125033 childlbl := childlbl+1;
%p A125033 od;
%p A125033 npar := [op(parents),childlbl];
%p A125033 if nops(counts) < lvl+1 then
%p A125033 counts := [op(counts),0];
%p A125033 fi;
%p A125033 counts := gen(npar,maxgen,counts,lvl+1);
%p A125033 childlbl := childlbl+1;
%p A125033 od;
%p A125033 fi;
%p A125033 if lvl <= maxgen -4 then
%p A125033 print(counts);
%p A125033 fi;
%p A125033 RETURN(counts);
%p A125033 end:
%p A125033 maxgen := 8;
%p A125033 parents := [1,2];
%p A125033 n := [1,0];
%p A125033 gen(parents,maxgen,n,2);
%p A125033 print(%) ; # _R. J. Mathar_, Nov 17 2006)
%p A125033 The following Maple10 code is from Alec Mihailovs: # (start)
%p A125033 f:=proc(n::integer[4],A::Array(datatype=integer[4]),
%p A125033 B::Array(datatype=integer[4]))::integer[4]; local c::integer[4],
%p A125033 i::integer[4],len::integer[4],m::integer[4]; c,len,m:=0,3,3;
%p A125033 while len>1 do if len=n then c:=c+1;m:=A[len];B[m]:=0;len:=len-1;
%p A125033 B[A[len]]:=B[A[len]]+1 elif B[A[len]]<=A[len] then for i from m+1
%p A125033 do if B[i]=0 then break fi od; len:=len+1;A[len]:=i;B[i]:=1;m:=2
%p A125033 else m:=A[len];B[m]:=0;len:=len-1;B[A[len]]:=B[A[len]]+1 fi od; c end:
%p A125033 cf:=Compiler:-Compile(f):
%p A125033 F:=proc(n::posint) local A,B;
%p A125033 if n<3 then 1 elif n=3 then 2 else
%p A125033 A:=Array([$1..3,0$(n-3)],datatype=integer[4]);
%p A125033 B:=Array([1$3,0$((n-2)*(n+1)/2)],datatype=integer[4]);
%p A125033 cf(n,A,B) fi end:
%p A125033 seq(F(n),n=1..12); # (end)
%K A125033 nonn
%O A125033 0,3
%A A125033 _Paul D. Hanna_ and _R. J. Mathar_, Nov 17 2006
%E A125033 Terms a(6)-a(10) from _R. J. Mathar_, Nov 17 2006
%E A125033 a(11) and a(12) from Alec Mihailovs (alec(AT)mihailovs.com), Nov 19 2006