|
|
A025147
|
|
Number of partitions of n into distinct parts >= 2.
|
|
89
|
|
|
1, 0, 1, 1, 1, 2, 2, 3, 3, 5, 5, 7, 8, 10, 12, 15, 17, 21, 25, 29, 35, 41, 48, 56, 66, 76, 89, 103, 119, 137, 159, 181, 209, 239, 273, 312, 356, 404, 460, 522, 591, 669, 757, 853, 963, 1085, 1219, 1371, 1539, 1725, 1933, 2164, 2418, 2702, 3016, 3362, 3746, 4171, 4637, 5155
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
COMMENTS
|
These "partitions of n into distinct parts >= k" and "partitions of n into distinct parts, the least being k-1" come in pairs of similar, almost shifted but not identical, sequences:
The distinction in the definitions is that "distinct parts >= k" sets a lower bound to all parts, whereas "the least being ..." means that the lower limit must be attained by one of the parts. (End)
Generating functions and Maple programs for the sequences in the first and second columns of the above list are respectively:
f:=proc(k) product(1+x^j, j=k..100): series(%,x,100): seriestolist(%); end;
g:=proc(k) x^(k-1)*product(1+x^j, j=k..100): series(%,x,100): seriestolist(%); end; (End)
Also number of partitions of n+1 into distinct parts, the least being 1.
Number of different sums from 1+[1,3]+[1,4]+...+[1,n]. - Jon Perry, Jan 01 2004
Also number of partitions of n such that if k is the largest part, then all parts from 1 to k occur, k occurring at least twice. Example: a(7)=3 because we have [2,2,2,1],[2,2,1,1,1] and [1,1,1,1,1,1,1]. - Emeric Deutsch, Apr 09 2006
Also number of partitions of n+1 such that if k is the largest part, then all parts from 1 to k occur, k occurring exactly once. Example: a(7)=3 because we have [3,2,2,1],[3,2,1,1,1] and [2,1,1,1,1,1,1] (there is a simple bijection with the partitions defined before). - Emeric Deutsch, Apr 09 2006
Also number of partitions of n+1 into distinct parts where the number of parts is itself a part. - Reinhard Zumkeller, Nov 04 2007
Trivially, number of partitions of n into distinct parts (as ascending lists) such that the first part is not 1, the second not 2, the third not 3, etc., see example. - Joerg Arndt, Jun 10 2013
|
|
REFERENCES
|
Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education, Vol. 31, No. 1, pp. 24-28, Winter 1997. MathEduc Database (Zentralblatt MATH, 1997c.01891).
Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17. Zentralblatt MATH, Zbl 1071.05501.
|
|
LINKS
|
|
|
FORMULA
|
G.f.: Product_{k>=2} (1+x^k).
a(n)=t(n, 1), where t(n, k)=1+Sum_{i>j>k and i+j=n} t(i, j), 2<=k<=n. - Reinhard Zumkeller, Jan 01 2003
G.f.: 1 + Sum_{k=1..infinity} (x^(k*(k+3)/2) / Product_{j=1..k} (1-x^j)). - Emeric Deutsch, Apr 09 2006
The previous g.f. is a special case of the g.f. for partitions into distinct parts >= L, Sum_{n>=0} ( x^(n*(n+2*L-1)/2) / Product_{k=1..n} (1-x^k) ). - Joerg Arndt, Mar 24 2011
G.f.: Sum_{n>=1} ( x^(n*(n+1)/2-1) / Product_{k=1..n-1} (1-x^k) ), a special case of the g.f. for partitions into distinct parts >= L, Sum_{n>=L-1} ( x^(n*(n+1)/2-L*(L-1)/2) / Product_{k=1..n-(L-1)} (1-x^k) ). - Joerg Arndt, Mar 27 2011
a(n) ~ exp(Pi*sqrt(n/3)) / (8*3^(1/4)*n^(3/4)).
(End)
|
|
EXAMPLE
|
a(7) = 3, from {{3, 4}, {2, 5}, {7}}
There are a(17) = 21 partitions of 17 into distinct parts >=2:
01: [ 2 3 4 8 ]
02: [ 2 3 5 7 ]
03: [ 2 3 12 ]
04: [ 2 4 5 6 ]
05: [ 2 4 11 ]
06: [ 2 5 10 ]
07: [ 2 6 9 ]
08: [ 2 7 8 ]
09: [ 2 15 ]
10: [ 3 4 10 ]
11: [ 3 5 9 ]
12: [ 3 6 8 ]
13: [ 3 14 ]
14: [ 4 5 8 ]
15: [ 4 6 7 ]
16: [ 4 13 ]
17: [ 5 12 ]
18: [ 6 11 ]
19: [ 7 10 ]
20: [ 8 9 ]
21: [ 17 ]
(End)
|
|
MAPLE
|
g:=product(1+x^j, j=2..65): gser:=series(g, x=0, 62): seq(coeff(gser, x, n), n=0..57); # Emeric Deutsch, Apr 09 2006
with(combstruct):ZL := {L = PowerSet(Sequence(Z, card>=2)) }, unlabeled:seq(count([L, ZL], size=i), i=0..57); # Zerinvary Lajos, Mar 09 2007
|
|
MATHEMATICA
|
CoefficientList[Series[Product[1+q^n, {n, 2, 60}], {q, 0, 60}], q]
FoldList[ PartitionsQ[ #2+1 ]-#1&, 0, Range[ 64 ] ]
(* also *)
d[n_] := Select[IntegerPartitions[n], Max[Length /@ Split@#] == 1 && Min[#] >= 2 &]; Table[d[n], {n, 12}] (* strict partitions, parts >= 2 *)
Table[Length[d[n]], {n, 40}] (* A025147 for n >= 1 *)
p[_, 0] = 1; p[k_, m_] := p[k, m] = If[m < k, 0, p[k+1, m-k] + p[k+1, m]]; Table[p[2, m], {m, 0, 59}] (* Jean-François Alcover, Apr 17 2014, after Reinhard Zumkeller *)
|
|
PROG
|
(Haskell)
a025147 = p 2 where
p _ 0 = 1
p k m = if m < k then 0 else p (k + 1) (m - k) + p (k + 1) m
(PARI) a(n)=if(n, my(v=partitions(n)); sum(i=1, #v, v[i][1]>1&&v[i]==vecsort(v[i], , 8)), 1) \\ Charles R Greathouse IV, Nov 20 2012
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|