A052889 Number of rooted set partitions.

0, 1, 2, 6, 20, 75, 312, 1421, 7016, 37260, 211470, 1275725, 8142840, 54776761, 387022118, 2863489830, 22127336720, 178162416499, 1491567656472, 12959459317021, 116654844101140, 1086207322942812, 10447135955448522, 103654461984288429, 1059648140522024304

Offset: 0

Author

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Keywords

• easy
• nonn

Comments

Total number of blocks of size one in all set partitions of set {1..n}. - Wouter Meeussen, Jul 28 2003

With offset 1, number of permutations beginning with 12 and avoiding 12-3.

a(n) = number of partitions of {1...n+1} containing exactly one pair of consecutive integers, counted within a block. With offset t-1, number of partitions of {1...N} containing one string of t consecutive integers, where N=n+j, t=2+j, j = 0,1,2,.... - Augustine O. Munagi, Apr 10 2005

Examples

			a(3) = 6 because the partitions of {1, 2, 3, 4} containing a pair of consecutive integers are 124/3, 134/2, 14/23, 12/3/4, 1/23/4, 1/2/34.
		

Links

• Robert Israel, Table of n, a(n) for n = 0..575
• Adam M. Goyt and Lara K. Pudwell, Avoiding colored partitions of two elements in the pattern sense, arXiv preprint arXiv:1203.3786 [math.CO], 2012. - From _N. J. A. Sloane_, Sep 17 2012
• Jia Huang and Erkko Lehtonen, Associative-commutative spectra for some varieties of groupoids, arXiv:2401.15786 [math.CO], 2024. See p. 13.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 865
• Sergey Kitaev, Generalized pattern avoidance with additional restrictions, Sem. Lothar. Combinat. B48e (2003); arXiv:math/0205215 [math.CO].
• Sergey Kitaev and Toufik Mansour, Simultaneous avoidance of generalized patterns, arXiv:math/0205182 [math.CO], 2002.
• Augustine O. Munagi, Set Partitions with Successions and Separations, IJMMS 2005:3 (2005),451-463.

Crossrefs

Cf. A000110.

Second column of triangle A033306.

Column k=1 of A175757.

Programs

Magma

[n eq 0 select 0 else n*Bell(n-1): n in [0..30]]; // G. C. Greubel, May 11 2024

Maple

spec := [S,{B=Set(C),C=Set(Z,1 <= card),S=Prod(Z,B)},labeled]: seq(combstruct[count](spec,size=n), n=0..20);
Explanation of above combstruct commands using generating functions, from Mitch Harris, Jul 28 2003:
Z = an atom (each atom used is labeled), gf: Z(x) = x
C = Set(Z, card <= 1) is the set of positive integers; gf: C(x) = e^(Z(x)) - 1 = e^x - 1 (the -1 removes the empty set); [x^n]C = 1 means there is exactly one set with n atoms since each atom is labeled
B = Set(C) the set of (ordered) sets of integers = ordered set partitions; gf: B(x) = e^C(x) = e^(e^x - 1)
S = Prod(Z, B) pairs of an atom (Z) and an ordered set partition = an ordered set partition with an adjoining single atom. The adjoining atom corresponds to choosing a "root" in the partition; gf: S(x) = x B(x) = x*e^(e^x-1)
A052889 := n -> `if`(n=0,0,n*combinat[bell](n-1)):
seq(A052889(n),n=0..20); # Peter Luschny, Apr 19 2011

Mathematica

Range[0, 20]! CoefficientList[Series[ x Exp[Exp[x]-1], {x, 0, 20}], x] (* Geoffrey Critzer, Nov 25 2011 *)
Table[If[n==0, 0, n*BellB[n-1]], {n,0,30}] (* G. C. Greubel, May 11 2024 *)

SageMath

[0]+[n*bell_number(n-1) for n in range(1,31)] # G. C. Greubel, May 11 2024

Formula

E.g.f.: x*exp(exp(x)-1).

a(n) = n*A000110(n-1). - Vladeta Jovovic, Sep 14 2003

Let A be the upper Hessenberg matrix of order n defined by: A[i,i-1]=-1, A[i,j]=binomial(j-1,i-1), (i<=j), and A[i,j]=0 otherwise. Then, for n>=1, a(n)=(-1)^(n-1)*coeff(charpoly(A,x),x). - Milan Janjic, Jul 08 2010