Advanced Search
All Posts : MaplePrimes Commons General Technical Discussions

A125033

Alec Mihailovs 4485
November 19 2006
0
Sequence A125033 in the OEIS submitted by Paul D. Hanna and Richard J. Mathar, is defined as 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'. The example given there shows how to obtain first 5 elements: 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]; I used the following back-tracking procedure to calculate it, 
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);

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

        1213504295
That confirms Richard Mathar's and Paul Hanna's calculations and gives one more element of the sequence. Further elements could not be calculated on my 32-bit computer using this procedure, because they are greater than 2^32. Changing the types of c and f from integer[4] to float[8] allows further calculations. I did that and after about an hour got the next element, 
F(13);
                      24606397802
Alec Mihailovs http://mihailovs.com/Alec/
assign integer

Please Wait...