cp's OEIS Frontend

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

%I A025147 #86 Nov 09 2023 12:20:10
%S A025147 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,
%T A025147 103,119,137,159,181,209,239,273,312,356,404,460,522,591,669,757,853,
%U A025147 963,1085,1219,1371,1539,1725,1933,2164,2418,2702,3016,3362,3746,4171,4637,5155
%N A025147 Number of partitions of n into distinct parts >= 2.
%C A025147 From _R. J. Mathar_, Jul 31 2008: (Start)
%C A025147 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:
%C A025147 A025147, A096765 (k=2)
%C A025147 A025148, A096749 (k=3)
%C A025147 A025149, A026824 (k=4)
%C A025147 A025150, A026825 (k=5)
%C A025147 A025151, A026826 (k=6)
%C A025147 A025152, A026827 (k=7)
%C A025147 A025153, A026828 (k=8)
%C A025147 A025154, A026829 (k=9)
%C A025147 A025155, A026830 (k=10)
%C A025147 A096740, A026831 (k=11)
%C A025147 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)
%C A025147 From _N. J. A. Sloane_, Sep 28 2008: (Start)
%C A025147 Generating functions and Maple programs for the sequences in the first and second columns of the above list are respectively:
%C A025147 For A025147, A025148, etc.:
%C A025147 f:=proc(k) product(1+x^j, j=k..100): series(%,x,100): seriestolist(%); end;
%C A025147 For A096765, A096749, etc.:
%C A025147 g:=proc(k) x^(k-1)*product(1+x^j, j=k..100): series(%,x,100): seriestolist(%); end; (End)
%C A025147 Also number of partitions of n+1 into distinct parts, the least being 1.
%C A025147 Number of different sums from 1+[1,3]+[1,4]+...+[1,n]. - _Jon Perry_, Jan 01 2004
%C A025147 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
%C A025147 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
%C A025147 Also number of partitions of n+1 into distinct parts where the number of parts is itself a part. - _Reinhard Zumkeller_, Nov 04 2007
%C A025147 Partial sums give A038348 (observed by _Jonathan Vos Post_, proved by several correspondents).
%C A025147 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
%C A025147 Convolution with A033999 gives A270144 (apart from the offset). - _R. J. Mathar_, Jun 18 2016
%D A025147 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).
%D A025147 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.
%H A025147 Alois P. Heinz, <a href="/A025147/b025147.txt">Table of n, a(n) for n = 0..10000</a> (terms n = 0..100 from Reinhard Zumkeller)
%H A025147 Kevin Beanland and Hung Viet Chu, <a href="https://arxiv.org/abs/2311.01926">On Schreier-type Sets, Partitions, and Compositions</a>, arXiv:2311.01926 [math.CO], 2023.
%H A025147 Rebekah Ann Gilbert, <a href="http://www.math.uiuc.edu/~rgilber1/AFineRediscovery_Gilbert.pdf">A Fine Rediscovery</a>, 2014.
%H A025147 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=798">Encyclopedia of Combinatorial Structures 798</a>
%H A025147 Mircea Merca, <a href="http://dx.doi.org/10.1016/j.jnt.2015.08.014">Combinatorial interpretations of a recent convolution for the number of divisors of a positive integer</a>, Journal of Number Theory, Volume 160, March 2016, Pages 60-75, function q_1(n), see Corollary 3.7.
%F A025147 G.f.: Product_{k>=2} (1+x^k).
%F A025147 a(n) = A000009(n)-a(n-1) = Sum_{0<=k<=n} (-1)^k*A000009(n-k). - _Henry Bottomley_, May 09 2002
%F A025147 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
%F A025147 G.f.: 1 + Sum_{k=1..infinity} (x^(k*(k+3)/2) / Product_{j=1..k} (1-x^j)). - _Emeric Deutsch_, Apr 09 2006
%F A025147 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
%F A025147 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
%F A025147 a(n) = Sum_{1<k<=floor((n+2)/2)} A060016(n-k+1,k-1), for n>0. - _Reinhard Zumkeller_, Nov 04 2007
%F A025147 a(n) = A096765(n+1). - _R. J. Mathar_, Jul 31 2008
%F A025147 From _Vaclav Kotesovec_, Aug 16 2015: (Start)
%F A025147 a(n) ~ 1/2 * A000009(n).
%F A025147 a(n) ~ exp(Pi*sqrt(n/3)) / (8*3^(1/4)*n^(3/4)).
%F A025147 (End)
%e A025147 a(7) = 3, from {{3, 4}, {2, 5}, {7}}
%e A025147 From _Joerg Arndt_, Jun 10 2013: (Start)
%e A025147 There are a(17) = 21 partitions of 17 into distinct parts >=2:
%e A025147 01:  [ 2 3 4 8 ]
%e A025147 02:  [ 2 3 5 7 ]
%e A025147 03:  [ 2 3 12 ]
%e A025147 04:  [ 2 4 5 6 ]
%e A025147 05:  [ 2 4 11 ]
%e A025147 06:  [ 2 5 10 ]
%e A025147 07:  [ 2 6 9 ]
%e A025147 08:  [ 2 7 8 ]
%e A025147 09:  [ 2 15 ]
%e A025147 10:  [ 3 4 10 ]
%e A025147 11:  [ 3 5 9 ]
%e A025147 12:  [ 3 6 8 ]
%e A025147 13:  [ 3 14 ]
%e A025147 14:  [ 4 5 8 ]
%e A025147 15:  [ 4 6 7 ]
%e A025147 16:  [ 4 13 ]
%e A025147 17:  [ 5 12 ]
%e A025147 18:  [ 6 11 ]
%e A025147 19:  [ 7 10 ]
%e A025147 20:  [ 8 9 ]
%e A025147 21:  [ 17 ]
%e A025147 (End)
%p A025147 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
%p A025147 with(combstruct):ZL := {L = PowerSet(Sequence(Z,card>=2)) },unlabeled:seq(count([L,ZL],size=i),i=0..57); # _Zerinvary Lajos_, Mar 09 2007
%t A025147 CoefficientList[Series[Product[1+q^n, {n, 2, 60}], {q, 0, 60}], q]
%t A025147 FoldList[ PartitionsQ[ #2+1 ]-#1&, 0, Range[ 64 ] ]
%t A025147 (* also *)
%t A025147 d[n_] := Select[IntegerPartitions[n], Max[Length /@ Split@#] == 1 && Min[#] >= 2 &]; Table[d[n], {n, 12}] (* strict partitions, parts >= 2 *)
%t A025147 Table[Length[d[n]], {n, 40}] (* A025147 for n >= 1 *)
%t A025147 (* _Clark Kimberling_, Mar 07 2014 *)
%t A025147 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_ *)
%o A025147 (Haskell)
%o A025147 a025147 = p 2 where
%o A025147    p _ 0 = 1
%o A025147    p k m = if m < k then 0 else p (k + 1) (m - k) + p (k + 1) m
%o A025147 -- _Reinhard Zumkeller_, Dec 28 2011
%o A025147 (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
%Y A025147 Cf. A015744, A015745, A015746, A015750, A015753, A015754, A015755, A002865.
%K A025147 nonn,easy,nice
%O A025147 0,6
%A A025147 _Clark Kimberling_
%E A025147 Corrected and extended by _Dean Hickerson_, Oct 10 2001