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,4

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.

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.

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

Example

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.

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

Prog

(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

Crossrefs

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

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

Sequence in context: A342558 A017863 A242634 * A029014 A304631 A298603

Adjacent sequences: A088564 A088565 A088566 * A088568 A088569 A088570

Keyword

nonn

Author

N. J. A. Sloane, Nov 30 2003

Status

approved