[seqfan] Re: Help with a tree sequence

[M. F. Hasler]

On Thu, May 21, 2020 at 3:08 AM Ali Sada wrote:

> Hi Everyone,
> I checked the original email I sent and it seems that the formatting
> changed. The "bonds" were not in the right places.

I apologize for that. Please check this image to see the possibilities of 3
> and 4.
> https://justpaste.it/5h040
>

Hi Ali,
If I understand correctly, instead of considering the whole tree, we can
keep track only of the list of  "unsaturated" numbers, i.e., the "leaves"
of the tree when we are at level n.
Since we always attach larger numbers, no branch will ever "end" because of
completely used bonds.
When we are done with n, the list of unsaturated numbers goes from n+1 to
the largest number M used so far in that tree.
(So M = n + number of leaves of the tree.)
More precisely, we only need to know the list of "free bonds" of each of
the numbers [n+1, ..., M] for a given tree :
if a number m was attached to its parent p with k (< p < m) "bonds", then
we only need to know m-k.
When we come to level m, all numbers < m appear earlier "inside" the tree
and have already been "saturated" with larger numbers.
So our list of leaves will start with m-k, the number of bonds remaining
for m, and the other leaves are the free bonds m'-k' of each of the larger
m' > m used in that tree, but these elements are irrelevant at level m
where we deal only with "m" (actually, m-k).
We will attach to this m
- either the new number (M+1) with all m-k bonds
- or (M+1) with m-k-1 bonds and (M+2) with 1 bond,
- or (M+1) with 1 bond and (M+2) with m-k-1 bonds,
- or ...
- or (M+1), ..., (M+m-k)  with 1 bonds each.
Each possibility corresponds to the choice of a vector V in the set S(m-k)
which is the union of
sets S(m-k,N), N=1,...,m-k,  of N-component vectors of positive integers
which sum to m-k.

This "attaching" means that we will remove m (now saturated) from the
beginning of the list,
and instead append to the list the numbers M+i-V[i], where i =1,2,..,N.
(They correspond to the number of remaining free bonds of the new numbers
M+i attached with V[i] bonds to their parent m.)

The following PARI program does this:

extend( T,n )={ /* extend the "tree" T (= list of (m-k)'s) at level n */
my( L=List() /* list of possibilities for this T*/, m_k = T[1], M = n+#T );
T=T[^1] /* elements m'-k', m'>m=n: we keep these and append m'-k' for the
new m' = M+i */;
for( N=1, m_k, /* to get all V with sum = m_k, we use V[i] = v[i+1]-v[i] >
0 with v[1]=0, v[N+1]=m_k */
 forvec( v=vector(N+1,i,[ if( i>N, m_k), if( i>1,m_k) ]), listput( L,
concat(T,vector(N,i, M+i-v[i+1]+v[i] )))
 ,2/* only strictly increasing vectors v*/)/* forvec(v) */ )/* for(N) */;
Vec(L)}

L=[[1]]; /* The list of "trees" (actually: (m-k)'s) we have at the
beginning of a new iteration. This [1] corresponds to 2 having 1 free bond
left */
a=List( #L ); /* a[n] = number of trees at step n. */
do_extend()={ listput(a, #L = concat([ extend(T, #a) | T <- L ]));
printf ( "At level %d, we get the new list %s.\n=> a(%d) = %d\n", #a, if (
50<#L, Str(L[1..10],"..."),L), #a, #L); }

(16:14) gp > do_extend()
At level 2, we get the new list [[2]]. /* This is the number of free bonds
of 3. */
=> a(2) = 1
(16:14) gp > do_extend()
At level 3, we get the new list [[2], [3, 4]]. /* Free bonds of 4, resp 4 &
5. */
=> a(3) = 2
(16:14) gp > do_extend()
At level 4, we get the new list [[3], [4, 5], [4, 3], [4, 5, 5], [4, 4, 6],
[4, 5, 6, 7]].
=> a(4) = 6
(16:14) gp > do_extend()
At level 5, we get the new list [[3], [5, 5], [4, 6], [5, 6, 7], [5, 3],
[5, 6, 5], [5, 5, 6], [5, 4, 7], [5, 6, 7, 7], [5, 6, 6, 8], [5, 5, 7, 8],
[5, 6, 7, 8, 9], [3, 3], [3, 6, 5], [3, 5, 6], [3, 4, 7], [3, 6, 7, 7], [3,
6, 6, 8], [3, 5, 7, 8], [3, 6, 7, 8, 9], [5, 5, 4], [5, 5, 7, 6], [5, 5, 6,
7], [5, 5, 5, 8], [5, 5, 7, 8, 8], [5, 5, 7, 7, 9], [5, 5, 6, 8, 9], [5, 5,
7, 8, 9, 10], [4, 6, 4], [4, 6, 7, 6], [4, 6, 6, 7], [4, 6, 5, 8], [4, 6,
7, 8, 8], [4, 6, 7, 7, 9], [4, 6, 6, 8, 9], [4, 6, 7, 8, 9, 10], [5, 6, 7,
5], [5, 6, 7, 8, 7], [5, 6, 7, 7, 8], [5, 6, 7, 6, 9], [5, 6, 7, 8, 9, 9],
[5, 6, 7, 8, 8, 10], [5, 6, 7, 7, 9, 10], [5, 6, 7, 8, 9, 10, 11]].
=> a(5) = 44
(16:14) gp > do_extend()
At level 6, we get the new list [[4], [6, 6], [5, 7], [6, 7, 8], [5, 3],
[5, 7, 5], [5, 6, 6], [5, 5, 7], [5, 4, 8], [5, 7, 8, 7]]....
=> a(6) = 524
(16:14) gp > do_extend()
At level 7, we get the new list [[4], [7, 6], [6, 7], [5, 8], [7, 8, 8],
[7, 7, 9], [6, 8, 9], [7, 8, 9, 10], [6, 3], [6, 8, 5]]....
=> a(7) = 12744
time = 110 ms.
(16:15) gp > #Set(L)
% = 9832

This means that among the 12744 possibilities, there are only 9832
inequivalent ones, considering the number of free bonds.
So we could save some computation time by using only the inequivalent ones,
and keep track of their multiplicity.
But still, this is a huge number ...
The sequence (1,1,2,6,44,524,12744,...) is not in OEIS, also not when we
divide by 2^[n/2], nor are the first differences.

- Maximilian