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

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, 77, 78, 95, 96, 114, 115, 138, 139, 163, 164, 194, 195, 226, 227, 266, 267, 307, 308, 357, 358, 408, 409, 471, 472, 535, 536, 612, 613, 690, 691, 785, 786, 881, 882, 995, 996, 1110, 1111

Offset: 0

Author

N. J. A. Sloane, Nov 30 2003

Keywords

• nonn

Comments

"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.

Examples

			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.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
• Paul Barry, Conjectures and results on some generalized Rueppel sequences, arXiv:2107.00442 [math.CO], 2021.
• Amanda Folsom et al., On a general class of non-squashing partitions, Discrete Mathematics 339.5 (2016): 1482-1506.
• Y. Homma, J. H. Ryu, and B. Tong, Sequence non-squashing partitions, Slides from a talk, 2014.
• O. J. Rodseth and J. A. Sellers, On a Restricted m-Non-Squashing Partition Function, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.4.
• N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, arXiv:math/0312418 [math.CO], 2003.
• N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, Discrete Math., 294 (2005), 259-274.

Crossrefs

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

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

Programs

Haskell

import Data.List (transpose)
a088567 n = a088567_list !! n
a088567_list = 1 : tail xs where
   xs = 0 : 1 : zipWith (+) xs (tail $ concat $ transpose [xs, tail xs])
-- Reinhard Zumkeller, Nov 15 2012

Maple

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;
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

Mathematica

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 *)

Formula

a(0)=1, a(1)=1; and for m >= 1, a(2m) = a(2m-1) + a(m) - 1, a(2m+1) = a(2m) + 1.

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).

G.f.: 1 + x/(1-x) + Sum_{k>=1} x^(3*2^(k-1))/Product_{j=0..k} (1-x^(2^j)).

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.)