|
Search: id:A088567
|
|
|
| A088567 |
|
a(n) = number of "non-squashing" partitions of n into distinct parts, that is, partitions n=p_1+p_2+...+p_k with 1 <= p_1 < p_2 < ... < p_k and p_1 + p_2 + ... + p_i <= p_{i+1} for all 1 <= i < k. |
|
+0
14
|
|
| 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; listen)
|
|
|
OFFSET
|
0,4
|
|
|
COMMENT
|
"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.
|
|
REFERENCES
|
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.
|
|
LINKS
|
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)).
Another 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
|
|
CROSSREFS
|
Cf. A000123, A088575, A088585, A088931. A090678 gives sequence mod 2.
Sequence in context: A008673 A133564 A017863 this_sequence A029014 A134345 A112193
Adjacent sequences: A088564 A088565 A088566 this_sequence A088568 A088569 A088570
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com), Nov 30 2003
|
|
|
Search completed in 0.002 seconds
|
