OFFSET
0,4
COMMENTS
Number of partitions p(1)+p(2)+...+p(m) = n (into positive parts) such that 2*p(k) <= p(k-1).
Number of partitions of n into parts of the form 2^j-1, j=1,2,... (called s-partitions). Example: a(7)=4 because we have [7], [3,3,1], [3,1,1,1,1] and [1,1,1,1,1,1,1]. - Emeric Deutsch, Mar 06 2006
One direction of a bijection between both sorts of partitions, as an algorithm: take a partition P (p(1)+p(2)+...+p(m) such that 2*p(k) <= p(k-1), m is the number of parts), subtract 1 from p(m), 2 from p(m-1), 4 from p(m-2), etc. (this gives a valid partition of the same type), add the part 2^m-1 to the other (initially empty) partition P', repeat until P is empty. The other direction goes by splitting parts 2^k-1 (uniquely) into distinct powers of 2 that are (in decreasing order) added at the left. - Joerg Arndt, Jan 06 2013
REFERENCES
Steenrod, N. and Epstein, D., Cohomology Operations, Princeton Univ. Press, 1962.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 513 terms from Reinhard Zumkeller)
P. C. P. Bhatt, An interesting way to partition a number, Inform. Process. Lett., 71, 1999, 141-148.
W. M. Y. Goh, P. Hitczenko and A. Shokoufandeh, s-partitions, Inform. Process. Lett., 82, 2002, 327-329.
Igor Pak, Complexity problems in enumerative combinatorics, arXiv:1803.06636 [math.CO], 2018.
FORMULA
G.f.: 1/Product_{i>=1} (1 - x^(2^i-1)). - Simon Plouffe (corrected by Joerg Arndt, Dec 28 2012)
a(n) = p(n,1) with p(n,k) = if k <= n then p(n-k,k) + p(n,2*k+1), otherwise 0^n. - Reinhard Zumkeller, Mar 18 2009
G.f.: Sum_{i>=0} x^(2^i-1) / Product_{j=1..i} (1 - x^(2^j-1)). - Ilya Gutkovskiy, Jun 05 2017
EXAMPLE
From Joerg Arndt, Dec 28 2012: (Start)
There are a(17)=13 partitions of 17 into Mersenne numbers:
[ 1] [ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ]
[ 2] [ 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ]
[ 3] [ 3 3 1 1 1 1 1 1 1 1 1 1 1 ]
[ 4] [ 3 3 3 1 1 1 1 1 1 1 1 ]
[ 5] [ 3 3 3 3 1 1 1 1 1 ]
[ 6] [ 3 3 3 3 3 1 1 ]
[ 7] [ 7 1 1 1 1 1 1 1 1 1 1 ]
[ 8] [ 7 3 1 1 1 1 1 1 1 ]
[ 9] [ 7 3 3 1 1 1 1 ]
[10] [ 7 3 3 3 1 ]
[11] [ 7 7 1 1 1 ]
[12] [ 7 7 3 ]
[13] [ 15 1 1 ]
There are a(17)=13 partitions p(1)+p(2)+...+p(m) = 17 such that 2*p(k) <= p(k-1):
[ 1] [ 10 4 2 1 ]
[ 2] [ 10 5 2 ]
[ 3] [ 11 4 2 ]
[ 4] [ 11 5 1 ]
[ 5] [ 12 4 1 ]
[ 6] [ 12 5 ]
[ 7] [ 13 3 1 ]
[ 8] [ 13 4 ]
[ 9] [ 14 2 1 ]
[10] [ 14 3 ]
[11] [ 15 2 ]
[12] [ 16 1 ]
[13] [ 17 ]
(End)
MAPLE
The sequence is C(n, n) where C := proc(m, n) option remember; local k, a; if m = 0 then if n = 0 then 1 else 0 fi; elif m > n then C(n, n); else a := 0; for k from 0 to m do a := a + C(floor(k/2), n-k) od; a; fi end;
g:=1/product(1-x^(2^k-1), k=1..10): gser:=series(g, x=0, 70): seq(coeff(gser, x, n), n=0..64); # Emeric Deutsch, Mar 06 2006
# alternative Maple program:
b:= proc(n, i) option remember; `if`(n=0, 1,
add(b(n-j, min(n-j, iquo(j, 2))), j=1..i))
end:
a:= n-> b(n$2):
seq(a(n), n=0..80); # Alois P. Heinz, Mar 14 2021
MATHEMATICA
nn = 63; CoefficientList[
Series[Product[1/(1 - x^(2^i - 1)), {i, 1, nn}], {x, 0, nn}], x] (* Geoffrey Critzer, Jul 09 2013 *)
PROG
(PARI)
N=166; q='q+O('q^N);
gf=1/prod(n=1, 1+ceil(log(N)/log(2)), 1-q^(2^n - 1) );
Vec(gf)
/* Joerg Arndt, Oct 06 2012 */
CROSSREFS
KEYWORD
nonn
AUTHOR
J. Daniel Christensen, Mar 15 1996
STATUS
approved