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,3

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.

Links

Table of n, a(n) for n=0..12.

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

Example

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

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)

Crossrefs

Sequence in context: A180271 A167199 A007889 * A034430 A143805 A249637

Adjacent sequences: A125030 A125031 A125032 * A125034 A125035 A125036

Keyword

nonn

Author

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

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

Status

approved