A078932 Number of compositions (ordered partitions) of n into powers of 3.

1, 1, 1, 2, 3, 4, 6, 9, 13, 20, 30, 44, 66, 99, 147, 219, 327, 487, 726, 1083, 1614, 2406, 3588, 5349, 7974, 11889, 17725, 26426, 39399, 58739, 87573, 130563, 194655, 290208, 432669, 645062, 961716, 1433814, 2137659, 3187014, 4751490, 7083951

Offset: 0

Author

Paul D. Hanna, Dec 16 2002

Keywords

• nonn

Examples

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..5000 (first 501 terms from T. D. Noe)

Crossrefs

Cf. A023359.

Cf. A087218, A087219.

Programs

Maple

a:= proc(n) option remember;
      `if`(n=0, 1, add(a(n-3^i), i=0..ilog[3](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-3^i], {i, 0, Log[3, n]}]]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Mar 23 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*=3; A=1/(1/subst(A,x,x^3)-x)); polcoeff(A,n))

PARI

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

Formula

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

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

Sum(k>=0, a(2k+1)*x^k) / sum(k>=0, a(2k)*x^k) = sum(k>=0, x^((3^n-1)/2)) = (1 +2x +4x^2 +9x^3 +20x^4 +...)/(1 +x +3x^2 +6x^3 +13x^4 +...) = (1 +x +x^4 +x^13 +x^40 +x^121 +...).

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

Extensions

New description from T. D. Noe, Jan 29 2007