login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A088567 Number of "non-squashing" partitions of n into distinct parts. 17
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 (list; graph; refs; listen; history; text; internal format)
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

Amanda Folsom et al, On a general class of non-squashing partitions, Discrete Mathematics 339.5 (2016): 1482-1506.

Y. Homma, J. H. Ryu, 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 12 16:18 EDT 2021. Contains 344959 sequences. (Running on oeis4.)