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,4

Links

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

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

Example

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 +...

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 *)

Prog

(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 */

Crossrefs

Cf. A023359.

Cf. A087218, A087219.

Sequence in context: A355909 A136423 A215245 * A206740 A172161 A117791

Adjacent sequences: A078929 A078930 A078931 * A078933 A078934 A078935

Keyword

nonn

Author

Paul D. Hanna, Dec 16 2002

Extensions

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

Status

approved