A025147 Number of partitions of n into distinct parts >= 2.

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

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• easy
• nice

Comments

From R. J. Mathar, Jul 31 2008: (Start)

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:

A025147, A096765 (k=2)

A025148, A096749 (k=3)

A025149, A026824 (k=4)

A025150, A026825 (k=5)

A025151, A026826 (k=6)

A025152, A026827 (k=7)

A025153, A026828 (k=8)

A025154, A026829 (k=9)

A025155, A026830 (k=10)

A096740, A026831 (k=11)

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)

From N. J. A. Sloane, Sep 28 2008: (Start)

Generating functions and Maple programs for the sequences in the first and second columns of the above list are respectively:

For A025147, A025148, etc.:

f:=proc(k) product(1+x^j, j=k..100): series(%,x,100): seriestolist(%); end;

For A096765, A096749, etc.:

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

Partial sums give A038348 (observed by Jonathan Vos Post, proved by several correspondents).

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

Convolution with A033999 gives A270144 (apart from the offset). - R. J. Mathar, Jun 18 2016

Examples

			a(7) = 3, from {{3, 4}, {2, 5}, {7}}
From _Joerg Arndt_, Jun 10 2013: (Start)
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)
		

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

• Alois P. Heinz, Table of n, a(n) for n = 0..10000 (terms n = 0..100 from Reinhard Zumkeller)
• Kevin Beanland and Hung Viet Chu, On Schreier-type Sets, Partitions, and Compositions, arXiv:2311.01926 [math.CO], 2023.
• Rebekah Ann Gilbert, A Fine Rediscovery, 2014.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 798
• Mircea Merca, Combinatorial interpretations of a recent convolution for the number of divisors of a positive integer, Journal of Number Theory, Volume 160, March 2016, Pages 60-75, function q_1(n), see Corollary 3.7.

Crossrefs

Cf. A015744, A015745, A015746, A015750, A015753, A015754, A015755, A002865.

Programs

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
-- Reinhard Zumkeller, Dec 28 2011

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 *)
(* Clark Kimberling, Mar 07 2014 *)
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 *)

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

Formula

G.f.: Product_{k>=2} (1+x^k).

a(n) = A000009(n)-a(n-1) = Sum_{0<=k<=n} (-1)^k*A000009(n-k). - Henry Bottomley, May 09 2002

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) = Sum_{1A060016(n-k+1,k-1), for n>0. - Reinhard Zumkeller, Nov 04 2007

a(n) = A096765(n+1). - R. J. Mathar, Jul 31 2008

From Vaclav Kotesovec, Aug 16 2015: (Start)

a(n) ~ 1/2 * A000009(n).

a(n) ~ exp(Pi*sqrt(n/3)) / (8*3^(1/4)*n^(3/4)).

(End)

Extensions

Corrected and extended by Dean Hickerson, Oct 10 2001