login
Total number of parts in all partitions of n. Also, sum of largest parts of all partitions of n.
(Formerly M2552)
238

%I M2552 #243 Sep 17 2021 16:45:20

%S 0,1,3,6,12,20,35,54,86,128,192,275,399,556,780,1068,1463,1965,2644,

%T 3498,4630,6052,7899,10206,13174,16851,21522,27294,34545,43453,54563,

%U 68135,84927,105366,130462,160876,198014,242812,297201,362587,441546,536104,649791,785437,947812,1140945,1371173,1644136,1968379,2351597,2805218,3339869,3970648,4712040,5584141,6606438,7805507,9207637

%N Total number of parts in all partitions of n. Also, sum of largest parts of all partitions of n.

%C a(n) = degree of Kac determinant at level n as polynomial in the conformal weight (called h). (Cf. C. Itzykson and J.-M. Drouffe, Statistical Field Theory, Vol. 2, p. 533, eq.(98); reference p. 643, Cambridge University Press, (1989).) - _Wolfdieter Lang_

%C Also the number of one-element transitions from the integer partitions of n to the partitions of n-1 for labeled parts with the assumption that from any part z > 1 one can take an element of amount 1 in one way only. That means z is composed of z unlabeled parts of amount 1, i.e. z = 1 + 1 + ... + 1. E.g., for n=3 to n=2 we have a(3) = 6 and [111] --> [11], [111] --> [11], [111] --> [11], [12] --> [11], [12] --> [2], [3] --> [2]. For the case of z composed by labeled elements, z = 1_1 + 1_2 + ... + 1_z, see A066186. - _Thomas Wieder_, May 20 2004

%C Number of times a derivative of any order (not 0 of course) appears when expanding the n-th derivative of 1/f(x). For instance (1/f(x))'' = (2 f'(x)^2-f(x) f''(x)) / f(x)^3 which makes a(2) = 3 (by counting k times the k-th power of a derivative). - _Thomas Baruchel_, Nov 07 2005

%C Starting with offset 1, = the partition triangle A008284 * [1, 2, 3, ...]. - _Gary W. Adamson_, Feb 13 2008

%C Starting with offset 1 equals A000041: (1, 1, 2, 3, 5, 7, 11, ...) convolved with A000005: (1, 2, 2, 3, 2, 4, ...). - _Gary W. Adamson_, Jun 16 2009

%C Apart from initial 0 row sums of triangle A066633, also the Möbius transform is A085410. - _Gary W. Adamson_, Mar 21 2011

%C More generally, the total number of parts >= k in all partitions of n equals the sum of k-th largest parts of all partitions of n. In this case k = 1. Apart from initial 0 the first column of A181187. - _Omar E. Pol_, Feb 14 2012

%C Row sums of triangle A221530. - _Omar E. Pol_, Jan 21 2013

%C From _Omar E. Pol_, Feb 04 2021: (Start)

%C a(n) is also the total number of divisors of all positive integers in a sequence with n blocks where the m-th block consists of A000041(n-m) copies of m, with 1 <= m <= n. The mentioned divisors are also all parts of all partitions of n.

%C Apart from initial zero this is also as follows:

%C Convolution of A000005 and A000041.

%C Convolution of A006218 and A002865.

%C Convolution of A341062 and A000070.

%C Row sums of triangles A221531, A245095, A339258, A340525, A340529. (End)

%C Number of ways to choose a part index of an integer partition of n, i.e., partitions of n with a selected position. Selecting a part value instead of index gives A000070. - _Gus Wiseman_, Apr 19 2021

%D S. M. Luthra, On the average number of summands in partitions of n, Proc. Nat. Inst. Sci. India Part. A, 23 (1957), p. 483-498.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe and Vaclav Kotesovec, <a href="/A006128/b006128.txt">Table of n, a(n) for n = 0..10000</a> (terms 0..1000 from T. D. Noe)

%H Paul Erdős and Joseph Lehner, <a href="http://dx.doi.org/10.1215/S0012-7094-41-00826-8">The distribution of the number of summands in the partitions of a positive integer</a>, Duke Math. J. 8, (1941), 335-345.

%H John A. Ewell, <a href="http://www.fq.math.ca/Papers1/45-1/quartewell01_2007.pdf">Additive evaluation of the divisor function</a>, Fibonacci Quart. 45 (2007), no. 1, 22-25. See Table 1.

%H Guo-Niu Han, <a href="http://arxiv.org/abs/0804.1849">An explicit expansion formula for the powers of the Euler Product in terms of partition hook lengths</a>, arXiv:0804.1849 [math.CO], 2008; see p.27

%H I. Kessler and M. Livingston, <a href="http://dx.doi.org/10.1007/BF01303193">The expected number of parts in a partition of n</a>, Monatsh. Math. 81 (1976), no. 3, 203-212.

%H I. Kessler and M. Livingston, <a href="https://eudml.org/doc/177752">The expected number of parts in a partition of n</a>, Monatsh. Math. 81 (1976), no. 3, 203-212.

%H Martin Klazar, <a href="http://arxiv.org/abs/1808.08449">What is an answer? — remarks, results and problems on PIO formulas in combinatorial enumeration, part I</a>, arXiv:1808.08449 [math.CO], 2018.

%H Vaclav Kotesovec, <a href="/A006128/a006128.jpg">Graph - The asymptotic ratio</a>

%H Arnold Knopfmacher and Neville Robbins, <a href="http://www.plouffe.fr/OEIS/citations/robbinspart.pdf">Identities for the total number of parts in partitions of integers</a>, Util. Math. 67 (2005), 9-18.

%H S. M. Luthra, <a href="/A006128/a006128.pdf">On the average number of summands in partitions of n</a>, Proc. Nat. Inst. Sci. India Part. A, 23 (1957), p. 483-498.

%H C. L. Mallows & N. J. A. Sloane, <a href="/A006123/a006123.pdf">Emails, May 1991</a>

%H C. L. Mallows & N. J. A. Sloane, <a href="/A006123/a006123_1.pdf">Emails, Jun. 1991</a>

%H Ljuben Mutafchiev, <a href="https://arxiv.org/abs/1712.03233">On the Largest Part Size and Its Multiplicity of a Random Integer Partition</a>, arXiv:1712.03233 [math.PR], 2017.

%H Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/polpa408.jpg">Illustration of initial terms</a>

%H J. Sandor, D. S. Mitrinovic, B. Crstici, <a href="http://books.google.com/books?id=XT1-HjeXFgYC&amp;pg=PA495">Handbook of Number Theory I, Volume 1</a>, Springer, 2005, p. 495.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/q-PolygammaFunction.html">q-Polygamma Function</a>, <a href="http://mathworld.wolfram.com/q-PochhammerSymbol.html">q-Pochhammer Symbol</a>.

%H H. S. Wilf, <a href="http://www.math.upenn.edu/~wilf/website/Unified%20setting%20II.pdf">A unified setting for selection algorithms (II)</a>, Annals Discrete Math., 2 (1978), 135-148.

%F G.f.: Sum_{n>=1} n*x^n / Product_{k=1..n} (1-x^k).

%F G.f.: Sum_{k>=1} x^k/(1-x^k) / Product_{m>=1} (1-x^m).

%F a(n) = Sum_{k=1..n} k*A008284(n, k).

%F a(n) = Sum_{m=1..n} of the number of divisors of m * number of partitions of n-m.

%F Note that the formula for the above comment is a(n) = Sum_{m=1..n} d(m)*p(n-m) = Sum_{m=1..n} A000005(m)*A000041(n-m), if n >= 1. - _Omar E. Pol_, Jan 21 2013

%F Erdős and Lehner show that if u(n) denotes the average largest part in a partition of n, then u(n) ~ constant*sqrt(n)*log n.

%F a(n) = A066897(n) + A066898(n), n>0. - _Reinhard Zumkeller_, Mar 09 2012

%F a(n) = A066186(n) - A196087(n), n >= 1. - _Omar E. Pol_, Apr 22 2012

%F a(n) = A194452(n) + A024786(n+1). - _Omar E. Pol_, May 19 2012

%F a(n) = A000203(n) + A220477(n). - _Omar E. Pol_, Jan 17 2013

%F a(n) = Sum_{m=1..p(n)} A194446(m) = Sum_{m=1..p(n)} A141285(m), where p(n) = A000041(n), n >= 1. - _Omar E. Pol_, May 12 2013

%F a(n) = A198381(n) + A026905(n), n >= 1. - _Omar E. Pol_, Aug 10 2013

%F a(n) = O(sqrt(n)*log(n)*p(n)), where p(n) is the partition function A000041(n). - _Peter Bala_, Dec 23 2013

%F a(n) = Sum_{m=1..n} A006218(m)*A002865(n-m), n >= 1. - _Omar E. Pol_, Jul 14 2014

%F From _Vaclav Kotesovec_, Jun 23 2015: (Start)

%F Asymptotics (Luthra, 1957): a(n) = p(n) * (C*N^(1/2) + C^2/2) * (log(C*N^(1/2)) + gamma) + (1+C^2)/4 + O(N^(-1/2)*log(N)), where N = n - 1/24, C = sqrt(6)/Pi, gamma is the Euler-Mascheroni constant A001620 and p(n) is the partition function A000041(n).

%F The formula a(n) = p(n) * (sqrt(3*n/(2*Pi)) * (log(n) + 2*gamma - log(Pi/6)) + O(log(n)^3)) in the abstract of the article by Kessler and Livingston (cited also in the book by Sandor, p. 495) is incorrect!

%F Right is: a(n) = p(n) * (sqrt(3*n/2)/Pi * (log(n) + 2*gamma - log(Pi^2/6)) + O(log(n)^3))

%F or a(n) ~ exp(Pi*sqrt(2*n/3)) * (log(6*n/Pi^2) + 2*gamma) / (4*Pi*sqrt(2*n)).

%F (End)

%F G.f.: (log(1-x) + psi_x(1))/(log(x) * (x)_inf), where psi_q(z) is the q-digamma function, and (q)_inf is the q-Pochhammer symbol (the Euler function). - _Vladimir Reshetnikov_, Nov 17 2016

%F a(n) = Sum_{m=1..n} A341062(m)*A000070(n-m), n >= 1. - _Omar E. Pol_, Feb 05 2021 2014

%e For n = 4 the partitions of 4 are [4], [2, 2], [3, 1], [2, 1, 1], [1, 1, 1, 1]. The total number of parts is 12. On the other hand, the sum of the largest parts of all partitions is 4 + 2 + 3 + 2 + 1 = 12, equaling the total number of parts, so a(4) = 12. - _Omar E. Pol_, Oct 12 2018

%p g:= add(n*x^n*mul(1/(1-x^k), k=1..n), n=1..61):

%p a:= n-> coeff(series(g,x,62),x,n):

%p seq(a(n), n=0..61);

%p # second Maple program:

%p a:= n-> add(combinat[numbpart](n-j)*numtheory[tau](j), j=1..n):

%p seq(a(n), n=0..61); # _Alois P. Heinz_, Aug 23 2019

%t a[n_] := Sum[DivisorSigma[0, m] PartitionsP[n - m], {m, 1, n}]; Table[ a[n], {n, 0, 41}]

%t CoefficientList[ Series[ Sum[n*x^n*Product[1/(1 - x^k), {k, n}], {n, 100}], {x, 0, 100}], x]

%t a[n_] := Plus @@ Max /@ IntegerPartitions@ n; Array[a, 45] (* _Robert G. Wilson v_, Apr 12 2011 *)

%t Join[{0}, ((Log[1 - x] + QPolyGamma[1, x])/(Log[x] QPochhammer[x]) + O[x]^60)[[3]]] (* _Vladimir Reshetnikov_, Nov 17 2016 *)

%t Length /@ Table[IntegerPartitions[n] // Flatten, {n, 50}] (* _Shouvik Datta_, Sep 12 2021 *)

%o (PARI) f(n)= {local(v,i,k,s,t);v=vector(n,k,0);v[n]=2;t=0;while(v[1]<n, i=2;while(v[i]==0,i++);v[i]--;s=sum(k=i,n,k*v[k]); while(i>1,i--;s+=i*(v[i]=(n-s)\i));t+=sum(k=1,n,v[k]));t } /* _Thomas Baruchel_, Nov 07 2005 */

%o (PARI) a(n) = sum(m=1, n, numdiv(m)*numbpart(n-m)) \\ _Michel Marcus_, Jul 13 2013

%o (Haskell)

%o a006128 = length . concat . ps 1 where

%o ps _ 0 = [[]]

%o ps i j = [t:ts | t <- [i..j], ts <- ps t (j - t)]

%o -- _Reinhard Zumkeller_, Jul 13 2013

%o (Python)

%o from sympy import divisor_count, npartitions

%o def a(n): return sum([divisor_count(m)*npartitions(n - m) for m in range(1, n + 1)]) # _Indranil Ghosh_, Apr 25 2017

%o (GAP) List([0..60],n->Length(Flat(Partitions(n)))); # _Muniru A Asiru_, Oct 12 2018

%Y Cf. A093694, A008284, A000005, A066633, A085410, A046746, A209423, A285220, A336902, A336903.

%Y Main diagonal of A210485.

%Y Column k=1 of A256193.

%Y The version for normal multisets is A001787.

%Y The unordered version is A001792.

%Y The strict case is A015723.

%Y The version for factorizations is A066637.

%Y A000041 counts partitions.

%Y A000070 counts partitions with a selected part.

%Y A336875 counts compositions with a selected part.

%Y A339564 counts factorizations with a selected factor.

%Y Cf. A066186, A083710, A130689, A264401, A276024, A343341.

%K nonn,easy,nice

%O 0,3

%A _N. J. A. Sloane_, _Colin Mallows_