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

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

Offset: 0

Author

Paul D. Hanna and R. J. Mathar, Nov 17 2006

Keywords

• nonn

Comments

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

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

Examples

			Labels for 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];
		

Links

• Alec Mihailovs, A125033: Maple Program (non-recursive, uses little memory); Mapleprimes, Nov 19 2006.

Programs

Maple

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];
if nops(counts) < lvl+1 then
counts := [op(counts),0];
fi;
counts := gen(npar,maxgen,counts,lvl+1);
childlbl := childlbl+1;
od;
fi;
if lvl <= maxgen -4 then
print(counts);
fi;
RETURN(counts);
end:
maxgen := 8;
parents := [1,2];
n := [1,0];
gen(parents,maxgen,n,2);
print(%) ; # R. J. Mathar, Nov 17 2006)
The following Maple10 code is from Alec Mihailovs: # (start)
f:=proc(n::integer[4],A::Array(datatype=integer[4]),
B::Array(datatype=integer[4]))::integer[4]; local c::integer[4],
i::integer[4],len::integer[4],m::integer[4]; c,len,m:=0,3,3;
while len>1 do if len=n then c:=c+1;m:=A[len];B[m]:=0;len:=len-1;
B[A[len]]:=B[A[len]]+1 elif B[A[len]]<=A[len] then for i from m+1
do if B[i]=0 then break fi od; len:=len+1;A[len]:=i;B[i]:=1;m:=2
else m:=A[len];B[m]:=0;len:=len-1;B[A[len]]:=B[A[len]]+1 fi od; c end:
cf:=Compiler:-Compile(f):
F:=proc(n::posint) local A,B;
if n<3 then 1 elif n=3 then 2 else
A:=Array([$1..3,0$(n-3)],datatype=integer[4]);
B:=Array([1$3,0$((n-2)*(n+1)/2)],datatype=integer[4]);
cf(n,A,B) fi end:
seq(F(n),n=1..12); # (end)

Extensions

Terms a(6)-a(10) from R. J. Mathar, Nov 17 2006

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