login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000070 Sum_{k=0..n} p(k) where p(k) = number of partitions of k (A000041).
(Formerly M1054 N0396)
146
1, 2, 4, 7, 12, 19, 30, 45, 67, 97, 139, 195, 272, 373, 508, 684, 915, 1212, 1597, 2087, 2714, 3506, 4508, 5763, 7338, 9296, 11732, 14742, 18460, 23025, 28629, 35471, 43820, 53963, 66273, 81156, 99133, 120770, 146785, 177970, 215308, 259891, 313065, 376326, 451501 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Also the total number of all different integers in all partitions of n + 1. E.g., a(3)=7 because the partition of 4 comprises the sets {1},{1, 2},{2},{1, 3},{4} of different integers and their total number is 7. - Thomas Wieder, Apr 10 2004

With offset 1, also the number of 1's in all partitions of n. For example, 3 = 2+1 = 1+1+1, a(3) = (zero 1's) + (one 1's) + (three 1's), so a(3) = 4. - Naohiro Nomoto, Jan 09 2002. See the Riordan reference p. 184, last formula, first term, for a proof based on Fine's identity given in Riordan, p. 182 (20).

Also, number of partitions of n into parts when there are two kinds of parts of size one.

Also number of graphical forest partitions of 2n+2.

a(n) = count 2 for each partition of n and 1 for each decrement. E.g., the partitions of 4 are 4 (2), 31 (3), 22 (2), 211 (3) and 1111 (2). 2+3+2+3+2=12. This is related to the Ferrers representation. We can see that taking the Ferrers diagram for each partition of n and adding a new * to all available columns, we generate each partition of n+1, but with repeats (A058884). - Jon Perry, Feb 06 2004

Also the number of 1-transitions among all integer partitions of n. A 1-transition is the removal of a digit "1" from a partition containing at least one "1" and subsequent addition of that "1" to another digit in that partition. This other digit may be a "1" also, but all digits of equal amount are considered as undistinquishable (unlabeled). E.g., for n=6 one has the partition [1113] for which the following two 1-transitions are possible: [1113] --> [123] and [1113] --> [114]. The 1-transitions of n form a partial order (poset). For n=6 one has 12 1-transitions: [111111] --> [11112], [11112] --> [1113], [11112] --> [1122], [1113] --> [114], [1113] --> [123], [1122] --> [123], [1122] --> [222], [123] --> [33], [123] --> [24], [114] --> [15], [114] --> [24], [15] --> [6]. - Thomas Wieder, Mar 08 2005

Also number of partitions of 2n+1 where one of the parts is greater than n (also where there are more than n parts) and of 2n+2 where one of the parts is greater than n+1 (or with more than n+1 parts). - Henry Bottomley, Aug 01 2005

Equals left border of triangle A137633 - Gary W. Adamson, Jan 31 2008

Equals row sums of triangle A027293. - Gary W. Adamson, Oct 26 2008

Convolved with A010815 = [1,1,1,...]. n-th partial sum of A000041 convolved with A010815 = the binomial sequence starting (1, n, ...). - Gary W. Adamson, Nov 09 2008

Equals A036469 convolved with A035363. - Gary W. Adamson, Jun 09 2009

a(A004526(n)) = A025065(n). - Reinhard Zumkeller, Jan 23 2010

The subsequence of prime partial sums of partition numbers begins: a(1) = 2, a(3) = 7, a(5) = 19, a(8) = 67, a(9) = 97, a(10) = 139, a(13) = 373,a(18) = 1597, a(36) = 99133, a(46) = 646193, a(60) = 6639349, a(71) = 34751159, a(79) = 107427163, a(86) = 276046669, a(95) = 881650031, a(140) = 151365242593. - Jonathan Vos Post, Feb 10 2010

a(n) = if n <= 1 then A054225(1,n) else A054225(n,1). - Reinhard Zumkeller, Nov 30 2011

Also the total number of 1's among all hook-lengths in all partitions of n. E.g., a(4)=7 because hooks of the partitions of n=4 comprise the multisets {4,3,2,1},{4,2,1,1},{3,2,2,1},{4,1,2,1},{4,3,2,1} and their total number of 1's is 7. - T. Amdeberhan, Jun 03 2012

With offset 1, a(n) is also the difference between the sum of largest and the sum of second largest elements in all partitions of n. More generally, the number of occurrences of k in all partitions of n equals the difference between the sum of k-th largest and the sum of (k+1)st largest elements in all partitions of n. And more generally, the sum of the number of occurrences of k, k+1, k+2..k+m in all partitions of n equals the difference between the sum of k-th largest and the sum of (k+m+1)st largest elements in all partitions of n. - Omar E. Pol, Oct 25 2012

a(0) = 1 and 2*a(n-1) >= a(n) for all n > 0. Hence a(n) is a complete sequence. - Frank M Jackson, Apr 08 2013

a(n) is the number of conjugacy classes in the order-preserving, order-decreasing and (order-preserving and order-decreasing) injective transformation semigroups. - Ugbene Ifeanyichukwu, Jun 03 2015

a(n) is also the number of unlabeled subgraphs of the n-cycle C_n. For example, for n = 3, there are 3 unlabeled subgraphs of the triangle C_3 with 0 edges, 2 with 1 edge, 1 with 2 edges, and 1 with 3 edges (C_3 itself), so a(3) = 3 + 2 + 1 + 1 = 7. - John P. McSorley, Nov 21 2016

REFERENCES

H. Gupta, An asymptotic formula in partitions. J. Indian Math. Soc., (N. S.) 10 (1946) 73-76.

H. Gupta et al., Tables of Partitions. Royal Society Mathematical Tables, Vol. 4, Cambridge Univ. Press, 1958, p. 90.

R. Honsberger, Mathematical Gems III, M.A.A., 1985, p. 6.

A. M. Odlyzko, Asymptotic Enumeration Methods, p. 19

J. Riordan, Combinatorial Identities, Wiley, 1968, p. 199.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

Stanley, R. P., Exercise 1.26 in Enumerative Combinatorics, Vol. 1. Cambridge, England: Cambridge University Press, p. 59, 1999.

LINKS

T. D. Noe, Table of n, a(n) for n = 0..1000

L. Bracci, L. E. Picasso, A simple iterative method to write the terms of any order of perturbation theory in quantum mechanics, The European Physical Journal Plus, October 2012, 127:119, DOI 10.1140/epjp/i2012-12119-6. - From N. J. A. Sloane, Dec 31 2012

C. C. Cadogan, On partly ordered partitions of a positive integer, Fib. Quart., 9 (1971), 329-336.

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

M. S. Cheema and H. Gupta, Tables of Partitions of Gaussian Integers. National Institute of Sciences of India, Mathematical Tables, Vol. 1, New Delhi, 1956 (Annotated scanned pages from, plus a review)

P. Flajolet and B. Salvy, Euler sums and contour integral representations, Experimental Mathematics, Vol. 7 Issue 1 (1998)

D. Frank, C. D. Savage and J. A. Sellers, On the Number of Graphical Forest Partitions, Ars Combinatoria, Vol. 65 (2002), 33-37.

H. Fripertinger, Partitions of an Integer

Manosij Ghosh Dastidar and Sourav Sen Gupta, Generalization of a few results in Integer Partitions, arXiv preprint arXiv:1111.0094 [cs.DM], 2011.

Guo-Niu Han, Enumeration of Standard Puzzles

Guo-Niu Han, Enumeration of Standard Puzzles [Cached copy]

M. D. Hirschhorn, The number of 1's in the partitions of n, Fib. Q., 51 (2013), 326-329.

M. D. Hirschhorn, The number of different parts in the partitions of n, Fib. Q., 52 (2014), 10-15. See p. 11. - N. J. A. Sloane, Mar 25 2014

N. Hobson, Nick's Mathematical Puzzles, Partition identity (or a proof of Stanley's Theorem)

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 113

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 126

M. M. Mogbonju, O. A. Ojo, I. A. Ogunleke, Graphical Representation of Conjugacy Classes in the Order-Preserving Partial One-One Transformation Semigroup, International Journal of Science and Research (IJSR), Volume 3 Issue 12, December 2014.

G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

F. Ruskey, Combinatorial Objects Server

N. J. A. Sloane, Transforms

I. J. Ugbene & E. O. Eze & and S. O. Makanjuola, On the Number of Conjugacy Classes in the Injective Order-Decreasing Transformation Semigroup, Pacific Journal of Science and Technology, Volume 14. Number 1. May 2013 (Spring), pp. 182-186.

Eric Weisstein's World of Mathematics, Stanley's Theorem

FORMULA

Euler transform of [ 2, 1, 1, 1, 1, 1, 1, ...].

log(a(n)) ~ -3.3959 + 2.44613*Sqrt(n). - Robert G. Wilson v, Jan 11 2002

a(n) = (1/n)*Sum_{k=1..n} (sigma(k)+1)*a(n-k), n > 1, a(0)=1. - Vladeta Jovovic, Aug 22 2002

G.f.: (1/(1-x))*Product(1/(1-x^m)), m=1..inf.

Sequence seems to have the same parity as A027349. Comment from James A. Sellers, Mar 08 2006: that is true.

a(n) = (1+O(n^(-1/6)))/(2*C*sqrt(3n))*exp(C*sqrt(n)) where C=Pi*sqrt(2/3). - Benoit Cloitre, Aug 31 2004

a(n) = A000041(2n+1) - A110618(2n+1) = A000041(2n+2) - A110618(2n+2). - Henry Bottomley, Aug 01 2005

Row sums of triangle A133735. - Gary W. Adamson, Sep 22 2007

a(n) = A092269(n+1) - A195820(n+1). - Omar E. Pol, Oct 20 2011

a(n) = A181187(n+1,1) - A181187(n+1,2). - Omar E. Pol, Oct 25 2012

From Peter Bala, Dec 23 2013: (Start)

Gupta gives the asymptotic result a(n-1) ~ sqrt(6/Pi^2)* sqrt(n)*p(n), where p(n) is the partition function A000041(n).

Let P(2,n) denote the set of partitions of n into parts k >= 2.

a(n-2) = sum {parts k in all partitions in P(2,n)} phi(k), where phi(k) is the Euler totient function (see A000010). Using this result and Merten's theorem on the average order of the phi function, leads to the asymptotic result

a(n-2) ~ 6/Pi^2*n*(p(n) - p(n-1)) = 6/Pi^2*A138880(n) as n -> inf. (End)

a(n) ~ exp(Pi*sqrt(2*n/3)) / (2^(3/2)*Pi*sqrt(n)) * (1 + 11*Pi/(24*sqrt(6*n)) + (73*Pi^2 - 1584)/(6912*n)). - Vaclav Kotesovec, Oct 26 2016

a(n) = A024786(n+2) + A024786(n+1). - Vaclav Kotesovec, Nov 05 2016

EXAMPLE

G.f. = 1 + 2*x + 4*x^2 + 7*x^3 + 12*x^4 + 19*x^5 + 30*x^6 + 45*x^7 + 67*x^8 + ...

From Omar E. Pol, Oct 25 2012: (Start):

For n = 5 consider the partitions of n+1:

--------------------------------------

.                         Number

Partitions of 6           of 1's

--------------------------------------

6 .......................... 0

3 + 3 ...................... 0

4 + 2 ...................... 0

2 + 2 + 2 .................. 0

5 + 1 ...................... 1

3 + 2 + 1 .................. 1

4 + 1 + 1 .................. 2

2 + 2 + 1 + 1 .............. 2

3 + 1 + 1 + 1 .............. 3

2 + 1 + 1 + 1 + 1 .......... 4

1 + 1 + 1 + 1 + 1 + 1 ...... 6

------------------------------------

35-16 =                     19

.

The difference between the sum of the first column and the sum of the second column of the set of partitions of 6 is 35 - 16 = 19 and equals the number of 1's in all partitions of 6, so the 6th term of this sequence is a(5) = 19.

(End)

MAPLE

with(combinat): a:=n->add(numbpart(j), j=0..n): seq(a(n), n=0..44); # Zerinvary Lajos, Aug 26 2008

MATHEMATICA

CoefficientList[ Series[1/(1 - x)*Product[1/(1 - x^k), {k, 75}], {x, 0, 45}], x] (* Robert G. Wilson v, Jul 13 2004 *)

Table[ Count[ Flatten@ IntegerPartitions@ n, 1], {n, 45}] (* Robert G. Wilson v, Aug 06 2008 *)

Join[{1}, Accumulate[PartitionsP[Range[50]]]+1] (* _Harvey P. Dale, Mar 12 2013 *)

a[ n_] := SeriesCoefficient[ 1 / (1 - x) / QPochhammer[ x], {x, 0, n}]; (* Michael Somos, Nov 09 2013 *)

Accumulate[PartitionsP[Range[0, 49]]] (* George Beck, Oct 23 2014; typo fixed by Virgile Andreani, Jul 10 2016 *)

PROG

(PARI) {a(n) = if( n<0, 0, polcoeff( 1 / prod(m=1, n, 1 - x^m, 1 + x * O(x^n)) / (1 - x), n))}; /* Michael Somos, Nov 08 2002 */

(PARI) x='x+O('x^66); Vec(1/((1-x)*eta(x))) /* Joerg Arndt, May 15 2011 */

(PARI) a(n) = sum(k=0, n, numbpart(k)); \\ Michel Marcus, Sep 16 2016

(Haskell)

a000070 = p a028310_list where

   p _          0 = 1

   p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m

-- Reinhard Zumkeller, Nov 06 2012

(Sage)

def A000070_list(leng):

    p = [number_of_partitions(n) for n in range(leng)]

    return [add(p[:k+1]) for k in range(leng)]

A000070_list(45) # Peter Luschny, Sep 15 2014

CROSSREFS

A diagonal of A066633.

Also second column of A126442. - George Beck, May 07 2011

Row sums of triangle A092905.

Also row sums of triangle A261555. - Omar E. Pol, Sep 14 2016

Also row sums of triangle A278427. - John P. McSorley, Nov 25 2016

Cf. A014153, A024786, A026794, A026905, A058884, A093694, A133735, A137633, A010815, A027293, A035363, A028310, A000712, A000990.

Sequence in context: A036439 A175965 A035298 * A008609 A264392 A100823

Adjacent sequences:  A000067 A000068 A000069 * A000071 A000072 A000073

KEYWORD

nonn,easy,nice,changed

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 6 08:53 EST 2016. Contains 278775 sequences.