A210772 Number of partitions of 2^n into powers of 2 less than or equal to 8.

1, 2, 4, 10, 35, 165, 969, 6545, 47905, 366145, 2862209, 22632705, 180007425, 1435853825, 11470030849, 91693092865, 733276217345, 5865135816705, 46916791205889, 375317149057025, 3002468471537665, 24019472891510785, 192154683614691329, 1537233070859485185

Offset

0,2

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (15,-70,120,-64).

Formula

G.f.: -(12*x^5+11*x^4+30*x^3-44*x^2+13*x-1)/Product_{j=0..3} (2^j*x-1).

a(n) = [x^2^(n-1)] 1/(1-x) * 1/Product_{j=0..2} (1-x^(2^j)) for n>0.

a(n) = 1 + (11*2^(n-3))/3 + 2^(3*n-7)/3 + 4^(n-2) for n>1. - Colin Barker, Jan 26 2018

Example

a(3) = 10 because there are 10 partitions of 2^3 = 8 into powers of 2 less than or equal to 8: [1,1,1,1,1,1,1,1], [2,1,1,1,1,1,1], [2,2,1,1,1,1], [2,2,2,1,1], [2,2,2,2], [4,1,1,1,1], [4,2,1,1], [4,2,2], [4,4], [8].

Maple

a:= n-> `if`(n<2, 2^n, (Matrix(4, (i, j)-> `if`(i=j-1, 1, `if`(i=4,
     [-64, 120, -70, 15][j], 0)))^(n-2). <<4, 10, 35, 165>>)[1, 1]):
seq(a(n), n=0..30);

Mathematica

LinearRecurrence[{15, -70, 120, -64}, {1, 2, 4, 10, 35, 165}, 30] (* Harvey P. Dale, Aug 27 2022 *)

Prog

(PARI) Vec((1 - 13*x + 44*x^2 - 30*x^3 - 11*x^4 - 12*x^5) / ((1 - x)*(1 - 2*x)*(1 - 4*x)*(1 - 8*x)) + O(x^40)) \\ Colin Barker, Jan 26 2018

Crossrefs

Column k=3 of A152977.

Sequence in context: A189591 A189598 A156800 * A125859 A103854 A126941

Adjacent sequences: A210769 A210770 A210771 * A210773 A210774 A210775

Keyword

nonn,easy

Author

Alois P. Heinz, Mar 26 2012

Status

approved