Trees with Labeled Nodes that form Permutation of Positive Integers

[Alec Mihailovs]

From: "Richard Mathar" <mathar at strw.leidenuniv.nl>
Sent: Thursday, November 16, 2006 11:44 AM
>
> pdh> Date: Tue, 14 Nov 2006 23:04:51 -0500
> pdh> From: "Paul D. Hanna" <pauldhanna at juno.com>
> pdh> ...
> pdh> Number of labelled nodes in generation n of a rooted tree
> pdh> where a node with label k has k child nodes such that
> pdh> the label of each child node is the least unused label in
> pdh> the path from the root to that child node,
> pdh> and where root is labeled '1'.
> pdh>   ...
> pdh> Thus, the number of nodes in generation n begins:
> pdh> [1, 1, 2, 7, 36, 248, ...]
>
> [1, 1, 2, 7, 36, 248, 2157, 22761, 283220, 4068411, 66367834, ...]
>                                                    ^^^ 66367834 is Gen 10

Maple 10 can compile (some) procedures in C. I used the following 
back-tracking procedure,

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 D. 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/