A088567 - OEIS

%I #34 Oct 22 2021 12:05:11

%S 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 77,78,95,96,114,115,138,139,163,164,194,195,226,227,266,267,307,308,

%U 357,358,408,409,471,472,535,536,612,613,690,691,785,786,881,882,995,996,1110,1111

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

%C "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 Reinhard Zumkeller, <a href="/A088567/b088567.txt">Table of n, a(n) for n = 0..10000</a>

%H 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 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 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 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 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 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 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 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 G.f.: 1 + x/(1-x) + Sum_{k>=1} x^(3*2^(k-1))/Product_{j=0..k} (1-x^(2^j)).

%F 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 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 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 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 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 (Haskell)

%o import Data.List (transpose)

%o a088567 n = a088567_list !! n

%o a088567_list = 1 : tail xs where

%o    xs = 0 : 1 : zipWith (+) xs (tail $ concat $ transpose [xs, tail xs])

%o -- _Reinhard Zumkeller_, Nov 15 2012

%Y Cf. A000123, A088575, A088585, A088931, A089054. A090678 gives sequence mod 2.

%Y Cf. A187821 (non-squashing partitions of n into odd parts).

%K nonn

%O 0,4

%A _N. J. A. Sloane_, Nov 30 2003