A007837 Number of partitions of n-set with distinct block sizes.
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
Keywords
Examples
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)
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..700
- 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.
- Gus Wiseman, Sequences counting and ranking multiset partitions whose part lengths, sums, or averages are constant or strict.
Crossrefs
Programs
-
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 # second Maple program: 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 *)
-
PARI
{my(n=20); Vec(serlaplace(prod(k=1, n, (1+x^k/k!) + O(x*x^n))))} \\ Andrew Howroyd, Dec 21 2017
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
Extensions
More terms from Christian G. Bower
a(0)=1 prepended by Alois P. Heinz, Aug 29 2015
Comments