|
|
A007837
|
|
Number of partitions of n-set with distinct block sizes.
|
|
101
|
|
|
1, 1, 1, 4, 5, 16, 82, 169, 541, 2272, 17966, 44419, 201830, 802751, 4897453, 52275409, 166257661, 840363296, 4321172134, 24358246735, 183351656650, 2762567051857, 10112898715063, 62269802986835, 343651382271526, 2352104168848091, 15649414071734847
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
Conjecture: the Gauss congruences a(n*p^k) == a(n*p^(k-1)) (mod p^k) hold for all primes p and positive integers n and k. Cf. A185895. - Peter Bala, Mar 17 2022
|
|
LINKS
|
Knopfmacher, A., Odlyzko, A. M., Pittel, B., Richmond, L. B., Stark, D., Szekeres, G. and Wormald, N. C., The asymptotic number of set partitions with unequal block sizes, Electron. J. Combin., 6 (1999), no. 1, Research Paper 2, 36 pp.
|
|
FORMULA
|
E.g.f.: Product_{m >= 1} (1+x^m/m!).
a(n) = Sum_{k=1..n} (n-1)!/(n-k)!*b(k)*a(n-k), where b(k) = Sum_{d divides k} (-d)*(-d!)^(-k/d) and a(0) = 1. - Vladeta Jovovic, Oct 13 2002
E.g.f.: exp(Sum_{k>=1} Sum_{j>=1} (-1)^(k+1)*x^(j*k)/(k*(j!)^k)). - Ilya Gutkovskiy, Jun 18 2018
|
|
EXAMPLE
|
The a(1) = 1 through a(5) = 16 set partitions with distinct block sizes:
{{1}} {{1,2}} {{1,2,3}} {{1,2,3,4}} {{1,2,3,4,5}}
{{1},{2,3}} {{1},{2,3,4}} {{1},{2,3,4,5}}
{{1,2},{3}} {{1,2,3},{4}} {{1,2},{3,4,5}}
{{1,3},{2}} {{1,2,4},{3}} {{1,2,3},{4,5}}
{{1,3,4},{2}} {{1,2,3,4},{5}}
{{1,2,3,5},{4}}
{{1,2,4},{3,5}}
{{1,2,4,5},{3}}
{{1,2,5},{3,4}}
{{1,3},{2,4,5}}
{{1,3,4},{2,5}}
{{1,3,4,5},{2}}
{{1,3,5},{2,4}}
{{1,4},{2,3,5}}
{{1,4,5},{2,3}}
{{1,5},{2,3,4}}
(End)
|
|
MAPLE
|
a:= proc(n) option remember; `if`(n=0, 1, add(add((-d)*(-d!)^(-k/d),
d=numtheory[divisors](k))*(n-1)!/(n-k)!*a(n-k), k=1..n))
end:
# second Maple program:
A007837 := proc(n) option remember; local k; `if`(n = 0, 1,
|
|
MATHEMATICA
|
nn=20; p=Product[1+x^i/i!, {i, 1, nn}]; Drop[Range[0, nn]!CoefficientList[ Series[p, {x, 0, nn}], x], 1] (* Geoffrey Critzer, Sep 22 2012 *)
a[0]=1; a[n_] := a[n] = Sum[(n-1)!/(n-k)!*DivisorSum[k, -#*(-#!)^(-k/#)&]* a[n-k], {k, 1, n}]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 23 2015, after Vladeta Jovovic *)
|
|
PROG
|
(PARI) {my(n=20); Vec(serlaplace(prod(k=1, n, (1+x^k/k!) + O(x*x^n))))} \\ Andrew Howroyd, Dec 21 2017
|
|
CROSSREFS
|
Cf. A000110, A005651, A007838, A032011, A035470, A038041, A178682, A265950, A271423, A275780, A326026, A326514, A326517, A326533.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|