cp's OEIS Frontend

A088567 Number of "non-squashing" partitions of n into distinct parts.

%I A088567 #34 Oct 22 2021 12:05:11
%S A088567 1,1,1,2,2,3,4,5,6,7,9,10,13,14,18,19,24,25,31,32,40,41,50,51,63,64,
%T A088567 77,78,95,96,114,115,138,139,163,164,194,195,226,227,266,267,307,308,
%U A088567 357,358,408,409,471,472,535,536,612,613,690,691,785,786,881,882,995,996,1110,1111
%N A088567 Number of "non-squashing" partitions of n into distinct parts.
%C A088567 "Non-squashing" refers to the property that p_1 + p_2 + ... + p_i <= p_{i+1} for all 1 <= i < k: if the parts are stacked in increasing size, at no point does the sum of the parts above a certain part exceed the size of that part.
%H A088567 Reinhard Zumkeller, <a href="/A088567/b088567.txt">Table of n, a(n) for n = 0..10000</a>
%H A088567 Paul Barry, <a href="https://arxiv.org/abs/2107.00442">Conjectures and results on some generalized Rueppel sequences</a>, arXiv:2107.00442 [math.CO], 2021.
%H A088567 Amanda Folsom et al., <a href="http://dx.doi.org/10.1016/j.disc.2015.12.019">On a general class of non-squashing partitions</a>, Discrete Mathematics 339.5 (2016): 1482-1506.
%H A088567 Y. Homma, J. H. Ryu, and B. Tong, <a href="http://sumry.yale.edu/sites/default/files/files/Sequence_nonsquashing_partitions.pdf">Sequence non-squashing partitions</a>, Slides from a talk, 2014.
%H A088567 O. J. Rodseth and J. A. Sellers, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Sellers/sellers75.html">On a Restricted m-Non-Squashing Partition Function</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.4.
%H A088567 N. J. A. Sloane and J. A. Sellers, <a href="https://arxiv.org/abs/math/0312418">On non-squashing partitions</a>, arXiv:math/0312418 [math.CO], 2003.
%H A088567 N. J. A. Sloane and J. A. Sellers, <a href="https://doi.org/10.1016/j.disc.2004.11.014">On non-squashing partitions</a>, Discrete Math., 294 (2005), 259-274.
%F A088567 a(0)=1, a(1)=1; and for m >= 1, a(2m) = a(2m-1) + a(m) - 1, a(2m+1) = a(2m) + 1.
%F A088567 Or, a(0)=1, a(1)=1; and for m >= 1, a(2m) = a(0)+a(1)+...+a(m)-1; a(2m+1) = a(0)+a(1)+...+a(m).
%F A088567 G.f.: 1 + x/(1-x) + Sum_{k>=1} x^(3*2^(k-1))/Product_{j=0..k} (1-x^(2^j)).
%F A088567 G.f.: Product_{n>=0} 1/(1-x^(2^n)) - Sum_{n >= 1} ( x^(2^n)/ ((1+x^(2^(n-1)))*Product_{j=0..n-1} (1-x^(2^j)) ) ). (The two terms correspond to A000123 and A088931 respectively.)
%e A088567 The partitions of n = 1 through 6 are: 1; 2; 3=1+2; 4=1+3; 5=1+4=2+3; 6=1+5=2+4=1+2+3.
%p A088567 f := proc(n) option remember; local t1,i; if n <= 2 then RETURN(1); fi; t1 := add(f(i),i=0..floor(n/2)); if n mod 2 = 0 then RETURN(t1-1); fi; t1; end;
%p A088567 t1 := 1 + x/(1-x); t2 := add( x^(3*2^(k-1))/ mul( (1-x^(2^j)),j=0..k), k=1..10); series(t1+t2, x, 256); # increase 10 to get more terms
%t A088567 max = 63; f = 1 + x/(1-x) + Sum[x^(3*2^(k-1))/Product[(1-x^(2^j)), {j, 0, k}], {k, 1, Log[2, max]}]; s = Series[f, {x, 0, max}] // Normal; a[n_] := Coefficient[s, x, n]; Table[a[n], {n, 0, max}] (* _Jean-François Alcover_, May 06 2014 *)
%o A088567 (Haskell)
%o A088567 import Data.List (transpose)
%o A088567 a088567 n = a088567_list !! n
%o A088567 a088567_list = 1 : tail xs where
%o A088567    xs = 0 : 1 : zipWith (+) xs (tail $ concat $ transpose [xs, tail xs])
%o A088567 -- _Reinhard Zumkeller_, Nov 15 2012
%Y A088567 Cf. A000123, A088575, A088585, A088931, A089054. A090678 gives sequence mod 2.
%Y A088567 Cf. A187821 (non-squashing partitions of n into odd parts).
%K A088567 nonn
%O A088567 0,4
%A A088567 _N. J. A. Sloane_, Nov 30 2003