Extend New Binary Sequence ?

[Max Alekseyev]

Paul,

Alternative definition of your sequence:

Let M be an infinite 01-matrix where element (i,j) is 1 iff i+j is odd
and i<=2*j:

010101010101...
101010101010...
010101010101...
001010101010...
000101010101...
001010101010...
000101010101...
...

Define a(n) as the sum of elements in the first column of M^n. Note
that there is only finite number of non-zero elements in the first
column of M^n (at most 2^n), so their summation is well-defined.

There is a straightforward connection to your original definition:
the (i,1)-th element of M^n equals the multiplicity of the leaf i in
the GEN.n tree.

To find an analytical formula for a(n) we need to come up with a
clever way of computing powers of the matrix M.

Regards,
Max

On 8/31/07, Paul D. Hanna <pauldhanna at juno.com> wrote:
>
>
>
> 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))
> > >
> >
> >
>
>