VOOZH about

URL: https://oeis.org/A007837

⇱ A007837 - OEIS

login
A007837
Number of partitions of n-set with distinct block sizes.
107
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
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
Philippe Flajolet, Éric Fusy, Xavier Gourdon, Daniel Panario and Nicolas Pouyanne, A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics, Fig. 3, arXiv:math/0606370 [math.CO], 2006.
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
From Gus Wiseman, Jul 13 2019: (Start)
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:
seq(a(n), n=0..30); # Alois P. Heinz, Sep 06 2008
# Alternative:
A007837 := proc(n) option remember; local k; `if`(n = 0, 1,
add(binomial(n-1, k-1) * A182927(k) * A007837(n-k), k = 1..n)) end:
seq(A007837(i), i=0..24); # Peter Luschny, Apr 25 2011
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
KEYWORD
nonn
EXTENSIONS
More terms from Christian G. Bower
a(0)=1 prepended by Alois P. Heinz, Aug 29 2015
STATUS
approved