A087221 Number of compositions (ordered partitions) of n into powers of 4.

1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 19, 26, 36, 50, 69, 96, 133, 184, 254, 352, 488, 676, 935, 1294, 1792, 2482, 3436, 4756, 6584, 9116, 12621, 17473, 24190, 33490, 46365, 64190, 88868, 123034, 170334, 235818, 326478, 451994, 625764, 866338, 1199400, 1660510

Offset: 0

Author

Paul D. Hanna, Aug 27 2003

Keywords

• nonn

Comments

Series trisections have a common ratio:

sum(k>=0, a(3k+1)*x^k) / sum(k>=0, a(3k)*x^k)

= sum(k>=0, a(3k+2)*x^k) / sum(k>=0, a(3k+1)*x^k)

= sum(k>=0, a(3k+3)*x^k) / sum(k>=0, a(3k+2)*x^k)

= sum(k>=0, x^((4^n-1)/3) ) = (1 + x + x^5 + x^21 + x^85 + x^341 +...).

Examples

			A(x) = A(x^4) + x*A(x^4)^2 + x^2*A(x^4)^3 + x^3*A(x^4)^4 + ...
= 1 +x + x^2 +x^3 +2x^4 +3x^5 +5x^6 +7x^7 + 10x^8 +...
		

Links

• T. D. Noe, Table of n, a(n) for n=0..500

Crossrefs

Cf. A078932, A087222, A087232, A087224. Different from A003269.

Programs

Maple

a:= proc(n) option remember;
      `if`(n=0, 1, add(a(n-4^i), i=0..ilog[4](n)))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Jan 11 2014

Mathematica

a[n_] := a[n] = If[n==0, 1, Sum[a[n-4^i], {i, 0, Log[4, n]}]]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Mar 24 2015, after Alois P. Heinz *)

PARI

a(n)=local(A,m); if(n<1,n==0,m=1; A=1+O(x); while(m<=n,m*=4; A=1/(1/subst(A,x,x^4)-x)); polcoeff(A,n))

PARI

N=66; x='x+O('x^N);
Vec( 1/( 1 - sum(k=0, ceil(log(N)/log(4)), x^(4^k)) ) )
/* Joerg Arndt, Oct 21 2012 */

Formula

G.f.: 1/( 1 - sum(k>=0, x^(4^k) ) ). [Joerg Arndt, Oct 21 2012]

G.f. satisfies A(x) = A(x^4)/(1 - x*A(x^4)), A(0) = 1.

a(n) ~ c * d^n, where d=1.384450093664460722709070772652942206959424183007359023442195..., c=0.526605891697738213614083414993893445498621299371909641096106... - Vaclav Kotesovec, May 01 2014