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

Author

Alois P. Heinz, Mar 26 2012

Keywords

• nonn
• easy

Examples

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

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

Crossrefs

Column k=3 of A152977.

Programs

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

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

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