A132880 a(n) = A000123( A000975(n-1) ) for n>=1 with a(0)=1, where A000123(n) = number of partitions of 2n into powers of 2 and A000975(n) = n-th number without consecutive equal binary digits.

1, 1, 2, 4, 14, 60, 450, 4964, 95982, 3037948, 170005730, 16522010532, 2882717916878, 902450057292988, 514768747418386946, 537142988843543963620, 1033976171696917695108270, 3688322935382700002945333884, 24514290054855626308893309022498

Offset

0,3

Links

Alois P. Heinz, Max Alekseyev and Dean Hickerson, Table of n, a(n) for n = 0..50 (terms 0..26 by Max Alekseyev and Dean Hickerson)

Formula

a(n) = A000123( (2^(n+1) + (-1)^n - 3)/6 ) for n>=0.

a(n) = a(n-1) + A000123( A000975(n-1) - 1) for n>0.

Example

Let b(n) = A000123(n) = number of partitions of 2n into powers of 2, then the initial terms of this sequence begin:
b(0), b(0), b(1), b(2), b(5), b(10), b(21), b(42), b(85), b(170),...
OSCILLATING PARITY TREE.
a(n) = number of nodes in generation n of the following tree.
Start at generation 0 with a single root node labeled [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 generations 0..5 of the tree begin as follows; the path from the root node is 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] .
Note: largest node label in generation n is A000975(n) + 1.

Maple

g:= proc(b, n) option remember; local t; if b<0 then 0 elif b=0 or n=0 then 1 elif b>=n then add (g(b-t, n) *binomial (n+1, t) *(-1)^(t+1), t=1..n+1) else g(b-1, n) +g(2*b, n-1) fi end: a:= proc(n) local m, t; m:= ceil (2 *(2^(n-1) -1) /3); t:= ilog2(2*m+1); g(m /2^(t-1), t) end: seq (a(n), n=0..30);  # Alois P. Heinz, Apr 17 2009

Mathematica

g[b_, n_] := g[b, n] = Module[{t}, Which[b<0, 0, b == 0 || n == 0, 1, b >= n, Sum[g[b-t, n]*Binomial[n+1, t]*(-1)^(t+1), {t, 1, n+1}], True, g[b-1, n] + g[2*b, n-1]]]; a[n_] := Module[{m, t}, m = Ceiling[2*(2^(n-1)-1) /3]; t = Log[2, 2*m+1] // Floor; g[m /2^(t-1), t]]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 11 2015, after Alois P. Heinz *)

Prog

(PARI) {A000123(n) = if(n<1, n==0, A000123(n\2) + A000123(n-1))}
{a(n) = A000123( (2^(n+1) + (-1)^n - 3)/6 )}

Crossrefs

Cf. A000123, A000975.

Sequence in context: A030808 A047009 A027740 * A019537 A046911 A089127

Adjacent sequences: A132877 A132878 A132879 * A132881 A132882 A132883

Keyword

nonn,changed

Author

Paul D. Hanna, Sep 11 2007

Status

approved