|
%I #59 Mar 15 2021 15:33:37
%S 1,1,1,2,2,2,3,4,4,5,6,6,7,8,9,11,12,13,15,16,17,20,22,23,26,28,29,32,
%T 35,37,41,45,47,51,55,58,63,68,72,77,82,86,92,98,103,111,118,123,131,
%U 139,145,154,164,171,180,190,198,208,219,229,241,253,264,278,291
%N Dimension of n-th degree part of Steenrod algebra.
%C Number of partitions p(1)+p(2)+...+p(m) = n (into positive parts) such that 2*p(k) <= p(k-1).
%C 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
%C 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
%D Steenrod, N. and Epstein, D., Cohomology Operations, Princeton Univ. Press, 1962.
%H Alois P. Heinz, <a href="/A000929/b000929.txt">Table of n, a(n) for n = 0..10000</a> (first 513 terms from Reinhard Zumkeller)
%H P. C. P. Bhatt, <a href="https://doi.org/10.1016/S0020-0190(99)00090-3">An interesting way to partition a number</a>, Inform. Process. Lett., 71, 1999, 141-148.
%H W. M. Y. Goh, P. Hitczenko and A. Shokoufandeh, <a href="https://doi.org/10.1016/S0020-0190(01)00300-3">s-partitions</a>, Inform. Process. Lett., 82, 2002, 327-329.
%H Igor Pak, <a href="https://arxiv.org/abs/1803.06636">Complexity problems in enumerative combinatorics</a>, arXiv:1803.06636 [math.CO], 2018.
%F G.f.: 1/Product_{i>=1} (1 - x^(2^i-1)). - _Simon Plouffe_ (corrected by _Joerg Arndt_, Dec 28 2012)
%F 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
%F G.f.: Sum_{i>=0} x^(2^i-1) / Product_{j=1..i} (1 - x^(2^j-1)). - _Ilya Gutkovskiy_, Jun 05 2017
%e From _Joerg Arndt_, Dec 28 2012: (Start)
%e There are a(17)=13 partitions of 17 into Mersenne numbers:
%e [ 1] [ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ]
%e [ 2] [ 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ]
%e [ 3] [ 3 3 1 1 1 1 1 1 1 1 1 1 1 ]
%e [ 4] [ 3 3 3 1 1 1 1 1 1 1 1 ]
%e [ 5] [ 3 3 3 3 1 1 1 1 1 ]
%e [ 6] [ 3 3 3 3 3 1 1 ]
%e [ 7] [ 7 1 1 1 1 1 1 1 1 1 1 ]
%e [ 8] [ 7 3 1 1 1 1 1 1 1 ]
%e [ 9] [ 7 3 3 1 1 1 1 ]
%e [10] [ 7 3 3 3 1 ]
%e [11] [ 7 7 1 1 1 ]
%e [12] [ 7 7 3 ]
%e [13] [ 15 1 1 ]
%e There are a(17)=13 partitions p(1)+p(2)+...+p(m) = 17 such that 2*p(k) <= p(k-1):
%e [ 1] [ 10 4 2 1 ]
%e [ 2] [ 10 5 2 ]
%e [ 3] [ 11 4 2 ]
%e [ 4] [ 11 5 1 ]
%e [ 5] [ 12 4 1 ]
%e [ 6] [ 12 5 ]
%e [ 7] [ 13 3 1 ]
%e [ 8] [ 13 4 ]
%e [ 9] [ 14 2 1 ]
%e [10] [ 14 3 ]
%e [11] [ 15 2 ]
%e [12] [ 16 1 ]
%e [13] [ 17 ]
%e (End)
%p 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;
%p 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
%p # alternative Maple program:
%p b:= proc(n, i) option remember; `if`(n=0, 1,
%p add(b(n-j, min(n-j, iquo(j, 2))), j=1..i))
%p end:
%p a:= n-> b(n$2):
%p seq(a(n), n=0..80); # _Alois P. Heinz_, Mar 14 2021
%t nn = 63; CoefficientList[
%t Series[Product[1/(1 - x^(2^i - 1)), {i, 1, nn}], {x, 0, nn}], x] (* _Geoffrey Critzer_, Jul 09 2013 *)
%o (PARI)
%o N=166; q='q+O('q^N);
%o gf=1/prod(n=1,1+ceil(log(N)/log(2)), 1-q^(2^n - 1) );
%o Vec(gf)
%o /* _Joerg Arndt_, Oct 06 2012 */
%Y Cf. A000225, A000041, A018819, A079559, A117145.
%K nonn
%O 0,4
%A _J. Daniel Christensen_, Mar 15 1996
|
