|
|
A005380
|
|
Expansion of 1 / Product_{k>=1} (1-x^k)^(k+1).
(Formerly M1601)
|
|
34
|
|
|
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
|
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.
|
|
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
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
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
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|