Extend New Binary Sequence ?

[Paul D. Hanna]

Max, 
    Ah, yes, the old "vectorization" trick - I should have thought of
that 
since I use it often myself.   Thank you once (or twice, or thrice)
again! 
 
What you computed are *conjectured* values of the number of nodes 
in generation n of the following tree.  
It would be nice to have a *proof*! 
  
DEFINITION. 
Start at generation 0 with a single node labelled '1'. 
 From then on, each parent node [k] is attached k child nodes 
with labels having opposite parity to k within the range {1..2k}. 
 
The initial 0..5 generations of the tree begin as follows; 
the paths along the nodes are given, followed by child nodes in []. 
GEN.0: [1] 
GEN.1: 1->[2] 
GEN.2: 1-2->[1,3]
GEN.3: 
1-2-1->[2]
1-2-3->[2,4,6]
GEN.4:
1-2-1-2->[1,3]
1-2-3-2->[1,3]
1-2-3-4->[1,3,5,7]
1-2-3-6->[1,3,5,7,9,11]
GEN.5:
1-2-1-2-1->[2]
1-2-1-2-3->[2,4,6]
1-2-3-2-1->[2]
1-2-3-2-3->[2,4,6]
1-2-3-4-1->[2]
1-2-3-4-3->[2,4,6]
1-2-3-4-5->[2,4,6,8,10]
1-2-3-4-7->[2,4,6,8,10,12,14]
1-2-3-6-1->[2]
1-2-3-6-3->[2,4,6]
1-2-3-6-5->[2,4,6,8,10]
1-2-3-6-7->[2,4,6,8,10,12,14]
1-2-3-6-9->[2,4,6,8,10,12,14,16,18]
1-2-3-6-11->[2,4,6,8,10,12,14,16,18,20,22]
 
As you can see, the number of nodes (and their sum) generate the 
initial terms  of the sequence: 
1, 1, 2, 4, 14, 60, 450, 4964, 95982, 3037948, 
(this was the extent of the counts done by my program).  
 
 From these counts, and by using the OEIS search tool (thanks to Ross
Cox!) 
I arrived at the conjecture that: 
  
The number of nodes in generation n = A000123( A000975(n-1) )  
where A000123(n) = number of partitions of 2n into powers of 2 
and A000975 = [0,1,2,5,10,21,42,85,170,...,(2^(n+2)-(-1)^n-3)/6,...]. 
 
Note that the largest term in generation n of the tree is A000975(n) + 1.
  
So, the conjecture is supported by intuition, but not by theory. 
 
Can anyone supply a proof (or a sketch of a proof)?  
 
Thanks, 
      Paul 
  
On Fri, 31 Aug 2007 18:24:24 -0700 "Max Alekseyev" <maxale at gmail.com>
writes:
> It is better first precompute and store values of A000123 using
> dynamic programming and then computation of your sequence become
> trivial:
> 
> ? N= (2^(26+1) + (-1)^26 - 3)/6
> ? a123=vector(N)
> ? a123[1]=2; for(n=2,N,a123[n]=a123[n\2]+a123[n-1])
> ? a(n) = if(n==0,1, if(n==1,1, a123[ (2^(n+1) + (-1)^n - 3)/6 ] ))
> ? vector(26,n,a(n))
> 
> The result is:
> 
> [1, 2, 4, 14, 60, 450, 4964, 95982, 3037948, 170005730, 
> 16522010532,
> 2882717916878, 902450057292988, 514768747418386946,
> 537142988843543963620, 1033976171696917695108270,
> 3688322935382700002945333884, 24514290054855626308893309022498,
> 304801526292655801235227790576374820,
> 7118057806591130565341301223201553053838,
> 313259388933361321062892077969687559682278460,
> 26062000616057795214066097831489188710729238725186,
> 4110314988488084452256619909138315265238808174186210404,
> 1232011347867422753097623155438444291235913527367600775244398,
> 703443704442715976354754937644920300954525944513753257422978632188,
>
766728692007699092343031760182847052574421909903729669942757487137772898]
> 
> Regards,
> Max
> 
> On 8/31/07, Paul D. Hanna <pauldhanna at juno.com> wrote:
> >
> >
> > Seqfans,
> >       To start with the correct offset (=0), the PARI program
> > should have been:
> >
> > A000123(n) = if(n<1, n==0, A000123(n\2) + A000123(n-1))
> >
> >
> > a(n) = if(n==0,1, A000123( (2^(n+1) + (-1)^n - 3)/6 ) )
> >
> > I do not know if there is any faster way of programming this ...
> > Perhaps I will find a matrix approach that will be quick?
> >
> > Thanks for any tips or tries in extending this sequence.
> >     Paul
> >
> > On Fri, 31 Aug 2007 19:48:11 -0400 Paul D. Hanna 
> <pauldhanna at juno.com>
> > writes:
> >
> >
> > The sequence begins:
> >
> > 1,1,2,4,14,60,450,4964,95982,3037948,
> >
> > but I can get no further before my old PARI gets "deep 
> recursion".
> >
> >
> > This is an equivalent definition using PARI:
> >
> > a(n) = if(n==0,1, A000123( (2^(n+2) - (-1)^n - 3)/6 ) )
> >
> > where
> > A000123(n) = if(n<1, n==0, A000123(n\2) + A000123(n-1))
> >
> 
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20070901/8fd89af5/attachment-0001.htm>