|
%I #64 Feb 01 2024 12:10:16
%S 0,1,2,6,20,75,312,1421,7016,37260,211470,1275725,8142840,54776761,
%T 387022118,2863489830,22127336720,178162416499,1491567656472,
%U 12959459317021,116654844101140,1086207322942812,10447135955448522,103654461984288429,1059648140522024304
%N Number of rooted set partitions.
%C Total number of blocks of size one in all set partitions of set {1..n}. - _Wouter Meeussen_, Jul 28 2003
%C With offset 1, number of permutations beginning with 12 and avoiding 12-3.
%C 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
%H Robert Israel, <a href="/A052889/b052889.txt">Table of n, a(n) for n = 0..575</a>
%H Adam M. Goyt and Lara K. Pudwell, <a href="http://arxiv.org/abs/1203.3786">Avoiding colored partitions of two elements in the pattern sense</a>, arXiv preprint arXiv:1203.3786 [math.CO], 2012. - From _N. J. A. Sloane_, Sep 17 2012
%H Jia Huang and Erkko Lehtonen, <a href="https://arxiv.org/abs/2401.15786">Associative-commutative spectra for some varieties of groupoids</a>, arXiv:2401.15786 [math.CO], 2024. See p. 13.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=865">Encyclopedia of Combinatorial Structures 865</a>
%H Sergey Kitaev, <a href="https://www.mat.univie.ac.at/~slc/wpapers/s48kitaev.html">Generalized pattern avoidance with additional restrictions</a>, Sem. Lothar. Combinat. B48e (2003); arXiv:math/0205215 [math.CO].
%H Sergey Kitaev and Toufik Mansour, <a href="https://arxiv.org/abs/math/0205182">Simultaneous avoidance of generalized patterns</a>, arXiv:math/0205182 [math.CO], 2002.
%H Augustine O. Munagi, <a href="http://www.emis.de/journals/HOA/IJMMS/2005/3451.pdf">Set Partitions with Successions and Separations</a>, IJMMS 2005:3 (2005),451-463.
%F E.g.f.: exp(exp(x)-1)*x.
%F a(n) = n*Bell(n-1). - _Vladeta Jovovic_, Sep 14 2003
%F 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
%e 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.
%p spec := [S,{B=Set(C),C=Set(Z,1 <= card),S=Prod(Z,B)},labeled]: seq(combstruct[count](spec,size=n), n=0..20);
%p Explanation of above combstruct commands using generating functions, from _Mitch Harris_, Jul 28 2003:
%p Z = an atom (each atom used is labeled), gf: Z(x) = x
%p 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
%p B = Set(C) the set of (ordered) sets of integers = ordered set partitions; gf: B(x) = e^C(x) = e^(e^x - 1)
%p 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)
%p A052889 := n -> `if`(n=0,0,n*combinat[bell](n-1)):
%p seq(A052889(n),n=0..20); # _Peter Luschny_, Apr 19 2011
%t a=Exp[x]-1; Range[0, 20]! CoefficientList[Series[ x Exp[a], {x, 0, 20}], x] (* _Geoffrey Critzer_, Nov 25 2011 *)
%Y Second column of triangle A033306.
%Y Cf. A000110.
%Y Column k=1 of A175757.
%K easy,nonn
%O 0,3
%A encyclopedia(AT)pommard.inria.fr, Jan 25 2000
|
