A115625 Number of partitions of {1,...,n} into block sizes a power of 2.

1, 1, 2, 4, 11, 31, 106, 372, 1500, 6220, 28696, 136016, 702802, 3727946, 21253324, 124231096, 772458367, 4918962479, 33061095118, 227303570524, 1639389365201, 12082068856285, 92951844299150, 729991789222972, 5960617085224012, 49637008114202876

Offset

0,3

Links

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

Formula

E.g.f.: exp(x+x^2/2+x^4/4!+x^8/8!+x^16/16!+...).

Maple

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(multinomial(n, n-i*j, i$j)/j!*
      b(n-i*j, i/2), j=0..n/i)))
    end:
a:= n-> b(n, 2^ilog2(n)):
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 17 2015
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add((j->
      a(n-j)*binomial(n-1, j-1))(2^i), i=0..ilog2(n)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Apr 21 2023

Mathematica

multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Sum[multinomial[n, Join[{n-i*j}, Array[i&, j]]]/j!*b[n - i*j, i/2], {j, 0, n/i}]]]; a[n_] := b[n, 2^Floor[Log[2, n]]]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Oct 29 2015, after Alois P. Heinz *)

Crossrefs

Cf. A018819, A115626.

Sequence in context: A110140 A190452 A275426 * A056323 A081557 A154603

Adjacent sequences: A115622 A115623 A115624 * A115626 A115627 A115628

Keyword

nonn

Author

Christian G. Bower, Jan 26 2006

Status

approved