|
|
A052889
|
|
Number of rooted set partitions.
|
|
13
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
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
|
|
LINKS
|
|
|
FORMULA
|
E.g.f.: exp(exp(x)-1)*x.
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
|
|
EXAMPLE
|
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.
|
|
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)):
|
|
MATHEMATICA
|
a=Exp[x]-1; Range[0, 20]! CoefficientList[Series[ x Exp[a], {x, 0, 20}], x] (* Geoffrey Critzer, Nov 25 2011 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
encyclopedia(AT)pommard.inria.fr, Jan 25 2000
|
|
STATUS
|
approved
|
|
|
|