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
KEYWORD
nonn,easy
AUTHOR
Alois P. Heinz, Mar 26 2012
STATUS
approved