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

%I #23 Mar 24 2015 06:22:16

%S 1,1,1,1,2,3,4,5,7,10,14,19,26,36,50,69,96,133,184,254,352,488,676,

%T 935,1294,1792,2482,3436,4756,6584,9116,12621,17473,24190,33490,46365,

%U 64190,88868,123034,170334,235818,326478,451994,625764,866338,1199400,1660510

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

%C Series trisections have a common ratio:

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

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

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

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

%H T. D. Noe, <a href="/A087221/b087221.txt">Table of n, a(n) for n=0..500</a>

%F G.f.: 1/( 1 - sum(k>=0, x^(4^k) ) ). [_Joerg Arndt_, Oct 21 2012]

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

%F a(n) ~ c * d^n, where d=1.384450093664460722709070772652942206959424183007359023442195..., c=0.526605891697738213614083414993893445498621299371909641096106... - _Vaclav Kotesovec_, May 01 2014

%e A(x) = A(x^4) + x*A(x^4)^2 + x^2*A(x^4)^3 + x^3*A(x^4)^4 + ...

%e = 1 +x + x^2 +x^3 +2x^4 +3x^5 +5x^6 +7x^7 + 10x^8 +...

%p a:= proc(n) option remember;

%p `if`(n=0, 1, add(a(n-4^i), i=0..ilog[4](n)))

%p end:

%p seq(a(n), n=0..50); # _Alois P. Heinz_, Jan 11 2014

%t 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_ *)

%o (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))

%o (PARI)

%o N=66; x='x+O('x^N);

%o Vec( 1/( 1 - sum(k=0, ceil(log(N)/log(4)), x^(4^k)) ) )

%o /* _Joerg Arndt_, Oct 21 2012 */

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

%K nonn

%O 0,5

%A _Paul D. Hanna_, Aug 27 2003