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

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005380 Expansion of 1 / Product_{k>=1} (1-x^k)^(k+1).
(Formerly M1601)
31
1, 2, 6, 14, 33, 70, 149, 298, 591, 1132, 2139, 3948, 7199, 12894, 22836, 39894, 68982, 117948, 199852, 335426, 558429, 922112, 1511610, 2460208, 3977963, 6390942, 10206862, 16207444, 25596941, 40214896, 62868772, 97814358 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Also, a(n) = number of partitions of the integer n where there are k+1 different kinds of part k for k = 1, 2, 3, ....

Also, a(n) = number of partitions of n objects of 2 colors. These are set partitions, the n objects are not labeled but colored, using two colors.  For each subset of size k there are k+1 different possibilities, i=0..k white and k-i black objects.

Also, a(n) = number of simple unlabeled graphs with n nodes of 2 colors whose components are complete graphs. - Geoffrey Critzer, Sep 27 2012

REFERENCES

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

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Exercise 7.99, p. 484 and pp. 548-549.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)

P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.

Vaclav Kotesovec, Graph - The asymptotic ratio

P. A. MacMahon, Memoir on symmetric functions of the roots of systems of equations, Phil. Trans. Royal Soc. London, 181 (1890), 481-536; Coll. Papers II, 32-87.

N. J. A. Sloane, Transforms

R. P. Stanley, Theory and Applications of Plane Partitions: Part 2, Studies in Appl. Math., 1 (1971), 259-279.

R. P. Stanley, The conjugate trace and trace of a plane partition, J. Combin. Theory, vol. A14 53-65 1973, esp. p. 64.

FORMULA

EULER transform of b(n) = n+1.

a(n) ~ Zeta(3)^(13/36) * exp(1/12 - Pi^4/(432*Zeta(3)) + Pi^2 * n^(1/3) / (3*2^(4/3)*Zeta(3)^(1/3)) + 3*Zeta(3)^(1/3) * n^(2/3) / 2^(2/3)) / (A * 2^(23/36) * 3^(1/2) * Pi * n^(31/36)), where A = A074962 = 1.2824271291... is the Glaisher-Kinkelin constant and Zeta(3) = A002117 = 1.202056903... . - Vaclav Kotesovec, Mar 07 2015

a(n) = A089353(n+m, m), n >= 1, for each m >= n. a(0) =1. See the Stanley reference, Exercise 7.99. - Wolfdieter Lang, Mar 09 2015

G.f.: exp(Sum_{k>=1} (sigma_1(k) + sigma_2(k))*x^k/k). - Ilya Gutkovskiy, Aug 11 2018

EXAMPLE

We represent each summand, k, in a partition of n as k identical objects. Then we color each object. We have no regard for the order of the colored objects.

a(3) = 14 because we have:  www; wwb; wbb; bbb; ww + w; ww + b;  wb + w; wb + b; bb + w; bb + b; w + w + w; w + w + b; w + b + b; b + b + b, where the 2 colors are black b and white w. - Geoffrey Critzer, Sep 27 2012

a(3) = 14 because we have:  3; 3'; 3''; 3'''; 2 + 1; 2 + 1';  2' + 1; 2' + 1'; 2'' + 1; 2'' + 1'; 1 + 1 + 1; 1 + 1 + 1'; 1 + 1' + 1'; 1' + 1' + 1', where a part k of different sorts is given as k, k', k'', etc. - Joerg Arndt, Mar 09 2015

From Alois P. Heinz, Mar 09 2015: (Start)

The a(4) = 33 = 5 + 9 + 6 + 8 + 5 partitions of 4 objects of 2 colors are:

5 partitions for the integer partition of 4 = 1 + 1 + 1 + 1:

  01: {{b}, {b}, {b}, {b}}

  02: {{b}, {b}, {b}, {w}}

  03: {{b}, {b}, {w}, {w}}

  04: {{b}, {w}, {w}, {w}}

  05: {{w}, {w}, {w}, {w}}

9 partitions for the integer partition of 4 = 1 + 1 + 2:

  06: {{b}, {b}, {b,b}}

  07: {{b}, {w}, {b,b}}

  08: {{w}, {w}, {b,b}}

  09: {{b}, {b}, {w,b}}

  10: {{b}, {w}, {w,b}}

  11: {{w}, {w}, {w,b}}

  12: {{b}, {b}, {w,w}}

  13: {{b}, {w}, {w,w}}

  14: {{w}, {w}, {w,w}}

6 partitions for the integer partition of 4 = 2 + 2:

  15: {{b,b}, {b,b}}

  16: {{b,b}, {w,b}}

  17: {{b,b}, {w,w}}

  18: {{w,b}, {w,b}}

  19: {{w,b}, {w,w}}

  20: {{w,w}, {w,w}}

8 partitions for the integer partition of 4 = 1 + 3:

  21: {{b}, {b,b,b}}

  22: {{w}, {b,b,b}}

  23: {{b}, {w,b,b}}

  24: {{w}, {w,b,b}}

  25: {{b}, {w,w,b}}

  26: {{w}, {w,w,b}}

  27: {{b}, {w,w,w}}

  28: {{w}, {w,w,w}}

5 partitions for the integer partition of 4 = 4:

  29: {{b,b,b,b}}

  30: {{w,b,b,b}}

  31: {{w,w,b,b}}

  32: {{w,w,w,b}}

  33: {{w,w,w,w}}

Some see number partitions, others see set partitions, ...

(End)

It is obvious from the example of Alois P. Heinz that a(n) enumerates multi-set partitions of a multi-set of n elements of two kinds. In the case that there is only one kind, this reduces to the usual case of numerical partitions. In the case that all the n elements are distinct, then this reduces to the case of set partitions. - Michael Somos, Mar 09 2015

There are a(3) = 14 plane partitions of 6 with trace 3; of 7 with trace 4; of 8 with trace 5; etc. See a formula above with the Stanley Exercise 7.99. - Wolfdieter Lang, Mar 09 2015

From Daniel Forgues, Mar 09 2015: (Start)

The a(3) = 14 = 4 + 6 + 4 partitions of 3 objects of 2 colors are:

4 partitions for the integer partition of 3 = 1 + 1 + 1:

  01: {{b}, {b}, {b}}

  02: {{b}, {b}, {w}}

  03: {{b}, {w}, {w}}

  04: {{w}, {w}, {w}}

6 partitions for the integer partition of 3 = 1 + 2:

  05: {{b}, {b,b}}

  06: {{w}, {b,b}}

  07: {{b}, {w,b}}

  08: {{w}, {w,b}}

  09: {{b}, {w,w}}

  10: {{w}, {w,w}}

4 partitions for the integer partition of 3 = 3:

  11: {{b,b,b}}

  12: {{w,b,b}}

  13: {{w,w,b}}

  14: {{w,w,w}}

The a(2) = 6 = 3 + 3 partitions of 2 objects of 2 colors are:

3 partitions for the integer partition of 2 = 1 + 1:

  01: {{b}, {b}}

  02: {{b}, {w}}

  03: {{w}, {w}}

3 partitions for the integer partition of 2 = 2:

  04: {{b,b}}

  05: {{w,b}}

  06: {{w,w}}

The a(1) = 2 partitions of 1 object of 2 colors are:

2 partitions for the integer partition of 1 = 1:

  01: {{b}}

  02: {{w}}

a(0) = 1: the empty partition, since empty sum is 0.

Triangle(sort of, since n_th row has p(n) = A000041 terms):

  1:  2

  2:  3, 3

  3:  4, 6, 4

  4:  5, 9, 6, 8, 5

  5:  6, ?, ?, ?, ?, ?, 6

  6:  7, ?, ?, ?, ?, ?, ?, ?, ?, ?, 7

Can we find a recurrence relation? (End)

MAPLE

mul( (1-x^i)^(-i-1), i=1..80); series(%, x, 80); seriestolist(%);

# second Maple program:

with(numtheory): etr:= proc(p) local b; b:=proc(n) option remember; local d, j; if n=0 then 1 else add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n fi end end: a:=etr(n-> n+1): seq(a(n), n=0..40); # Alois P. Heinz, Sep 08 2008

MATHEMATICA

max = 31; f[x_] = Product[ 1/(1-x^k)^(k+1), {k, 1, max}]; CoefficientList[ Series[ f[x], {x, 0, max}], x] (* Jean-François Alcover, Nov 08 2011, after g.f. *)

etr[p_] := Module[{b}, b[n_] := b[n] = Module[{d, j}, If[n==0, 1, Sum[ Sum[ d*p[d], {d, Divisors[j]}]*b[n-j], {j, 1, n}]/n]]; b]; a = etr[#+1&]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Nov 23 2015, after Alois P. Heinz *)

PROG

(PARI) a(n)=polcoeff(prod(i=1, n, (1-x^i+x*O(x^n))^-(i+1)), n)

CROSSREFS

Row sums of A054225.

Column k=2 of A075196.

Cf. A000219, A219555, A217093, A255050, A255052, A089353, A298988.

Sequence in context: A083404 A232497 A089351 * A257557 A124612 A230439

Adjacent sequences:  A005377 A005378 A005379 * A005381 A005382 A005383

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

Edited by Christian G. Bower, Sep 07 2002

New name from Joerg Arndt, Mar 09 2015

Restored 1995 name. - N. J. A. Sloane, Mar 09 2015

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 20 12:50 EST 2019. Contains 319330 sequences. (Running on oeis4.)