login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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, 1, 2, 7, 36, 248, 2157, 22761, 283220, 4068411, 66367834, 1213504295, 24606397802 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 20 13:14 EST 2020. Contains 332077 sequences. (Running on oeis4.)