A005380 Expansion of 1 / Product_{k>=1} (1-x^k)^(k+1).
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
Offset: 0
Examples
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)
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.
- Carlos A. A. Florentino, Plethystic exponential calculus and permutation polynomials, arXiv:2105.13049 [math.CO], 2021. Mentions this sequence.
- 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.
Crossrefs
Programs
-
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 *) -
PARI
a(n)=polcoeff(prod(i=1,n,(1-x^i+x*O(x^n))^-(i+1)),n)
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
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
Comments