|
|
A304969
|
|
Expansion of 1/(1 - Sum_{k>=1} q(k)*x^k), where q(k) = number of partitions of k into distinct parts (A000009).
|
|
39
|
|
|
1, 1, 2, 5, 11, 25, 57, 129, 292, 662, 1500, 3398, 7699, 17443, 39519, 89536, 202855, 459593, 1041267, 2359122, 5344889, 12109524, 27435660, 62158961, 140828999, 319065932, 722884274, 1637785870, 3710611298, 8406859805, 19046805534, 43152950024, 97768473163
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Also the number of ways to choose a multiset partition into distinct constant multisets of a multiset of length n that covers an initial interval of positive integers. This interpretation involves only multisets, not sequences. For example, the a(1) = 1 through a(4) = 11 multiset partitions are:
{{1}} {{1,1}} {{1,1,1}} {{1,1,1,1}}
{{1},{2}} {{1},{1,1}} {{1},{1,1,1}}
{{1},{2,2}} {{1,1},{2,2}}
{{2},{1,1}} {{1},{2,2,2}}
{{1},{2},{3}} {{2},{1,1,1}}
{{1},{2},{1,1}}
{{1},{2},{2,2}}
{{1},{2},{3,3}}
{{1},{3},{2,2}}
{{2},{3},{1,1}}
{{1},{2},{3},{4}}
The strongly normal non-strict version is A063834.
The strongly normal version is A270995.
(End)
|
|
LINKS
|
|
|
FORMULA
|
G.f.: 1/(1 - Sum_{k>=1} A000009(k)*x^k).
G.f.: 1/(2 - Product_{k>=1} (1 + x^k)).
G.f.: 1/(2 - Product_{k>=1} 1/(1 - x^(2*k-1))).
G.f.: 1/(2 - exp(Sum_{k>=1} (-1)^(k+1)*x^k/(k*(1 - x^k)))).
a(n) ~ c / r^n, where r = 0.441378990861652015438479635503868737167721352874... is the root of the equation QPochhammer[-1, r] = 4 and c = 0.4208931614610039677452560636348863586180784719323982664940444607322... - Vaclav Kotesovec, May 23 2018
|
|
EXAMPLE
|
a(n) is the number of ways to choose a strict integer partition of each part of an integer composition of n. The a(1) = 1 through a(4) = 11 choices are:
((1)) ((2)) ((3)) ((4))
((1)(1)) ((21)) ((31))
((1)(2)) ((1)(3))
((2)(1)) ((2)(2))
((1)(1)(1)) ((3)(1))
((1)(21))
((21)(1))
((1)(1)(2))
((1)(2)(1))
((2)(1)(1))
((1)(1)(1)(1))
(End)
|
|
MAPLE
|
b:= proc(n) option remember; `if`(n=0, 1, add(b(n-j)*add(
`if`(d::odd, d, 0), d=numtheory[divisors](j)), j=1..n)/n)
end:
a:= proc(n) option remember; `if`(n=0, 1,
add(b(j)*a(n-j), j=1..n))
end:
|
|
MATHEMATICA
|
nmax = 32; CoefficientList[Series[1/(1 - Sum[PartitionsQ[k] x^k, {k, 1, nmax}]), {x, 0, nmax}], x]
nmax = 32; CoefficientList[Series[1/(2 - Product[1 + x^k, {k, 1, nmax}]), {x, 0, nmax}], x]
nmax = 32; CoefficientList[Series[1/(2 - 1/QPochhammer[x, x^2]), {x, 0, nmax}], x]
a[0] = 1; a[n_] := a[n] = Sum[PartitionsQ[k] a[n - k], {k, 1, n}]; Table[a[n], {n, 0, 32}]
|
|
CROSSREFS
|
For partitions instead of compositions we have A270995, non-strict A063834.
A072233 counts partitions by sum and length.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|