|
| |
|
|
A000262
|
|
Number of "sets of lists": number of partitions of {1,...,n} into any number of lists, where a list means an ordered subset.
(Formerly M2950 N1190)
|
|
105
|
|
|
|
1, 1, 3, 13, 73, 501, 4051, 37633, 394353, 4596553, 58941091, 824073141, 12470162233, 202976401213, 3535017524403, 65573803186921, 1290434218669921, 26846616451246353, 588633468315403843, 13564373693588558173
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Determinant of n X n matrix M=[m(i,j)] where m(i,i)=i, m(i,j)=1 if i>j, m(i,j)=i-j if j>i. - Vladeta Jovovic, Jan 19 2003
a(n) = Sum_{k=0..n} |A008275(n,k)| * A000110(k). - Vladeta Jovovic, Feb 01 2003
a(n) = (n-1)!*LaguerreL(n-1,1,-1). - Vladeta Jovovic, May 10 2003
With p(n) = the number of integer partitions of n, d(i) = the number of different parts of the i-th partition of n, m(i,j) = multiplicity of the j-th part of the i-th partition of n, sum_{i=1}^{p(n)} = sum over i and prod_{j=1}^{d(i)} = product over j one has: a(n) = sum_{i=1}^{p(n)} n!/(prod_{j=1}^{d(i)} m(i,j)!) - Thomas Wieder, May 18 2005
Consider all n! permutations of the integer sequence [n] = 1,2,3,...,n. The i-th permutation, i=1,2,...,n!, consists of Z(i) permutation cycles. Such a cycle has the length lc(i,j), j=1,...,Z(i). For a given permutation we form the product of all its cycle lengths prod_{j=1}^{Z(i)} lc(i,j). Furthermore, we sum up all such products for all permutations of [n] which gives sum_{i=1 .. n!} prod_{j=1}^{Z(i)} lc(i,j) = A000262(n). For n=4 we have sum_{i=1 .. n!} prod_{j=1}^{Z(i)} lc(i,j) = 1*1*1*1 + 2*1*1 + 3*1 + 2*1*1 + 3*1 + 2*1 + 3*1 + 4 + 3*1 + 4 + 2*2 + 2*1*1 + 3*1 + 4 + 3*1 + 2*1*1 + 2*2 + 4 + 2*2 + 4 + 3*1 + 2*1*1 + 3*1 + 4 = 73 = A000262(4). - Thomas Wieder, Oct 06 2006
For a finite set S of size n, a chain gang G of S is a partially ordered set (S,<=) consisting only of chains. The number of chain gangs of S is a(n). For example, with S={a, b}and n=2, there are a(2)=3 chain gangs of S, namely, {(a,a),(b,b)}, {(a,a),(a,b),(b,b)} and {(a,a),(b,a),(b,b)}. - Dennis P. Walsh, Feb 22 2007
(-1)*A000262 with the first term set to 1 and A084358 form a reciprocal pair under the list partition transform and associated operations described in A133314. Cf. A133289. - Tom Copeland, Oct 21 2007
Consider the distribution of n unlabeled elements "1" onto n levels where empty levels are allowed. In addition, the empty levels are labeled. Their names are 0_1, 0_2, 0_3, etc. This sequence gives the total number of such distributions. If the empty levels are unlabeled ("0"), then the answer is A001700. Let the colon ":" separate two levels. Then, for example, for n=3 we have a(3)=13 arrangements: 111:0_1:0_2, 0_1:111:0_2, 0_1:0_2:111, 111:0_2:0_1, 0_2:111:0_1, 0_2:0_1:111, 11:1:0, 11:0:1, 0:11:1, 1:11:0, 1:0:11, 0:1:11, 1:1:1. - Thomas Wieder, May 25 2008
Row sums of exponential Riordan array [1,x/(1-x)]. - Paul Barry, Jul 24 2008
a(n) is the number of partitions of [n] (A000110) into lists of noncrossing sets. For example, a(3)=3 counts 12, 1-2, 2-1 and a(4) = 73 counts the 75 partitions of [n] into lists of sets (A000670) except for 13-24, 24-13 which fail to be noncrossing. - David Callan, Jul 25 2008
a(i-j)/(i-j)! gives the value of the non-null element (i, j) of the lower triangular matrix exp(S)/exp(1), where S is the lower triangular matrix - of whatever dimension - having all its (non-null) elements equal to one. [From Giuliano Ca rele (giulianoca rele(AT)tin.it), Aug 11 2008, Sep 07 2008]
a(n) is also the number of nilpotent partial one-one bijections (of an n-element set). Equivalently, it is the number of nilpotents in the symmetric inverse semigroup (monoid) [From Abdullahi Umar, Sep 14 2008]
A000262 is the exp transform of the factorial numbers A000142. [From Thomas Wieder, Sep 10 2008]
If n is a positive integer then the infinite continued fraction (1+n)/(1+(2+n)/(2+(3+n)/(3+...))) converges to the rational number A052852(n)/A000262(n). [David Angell (angell(AT)maths.unsw.edu.au), Dec 18 2008]
a(n) = exp(-1)*n!*M(n+1,2,1), n>=1, where M (=1F1) is the confluent hypergeometric function of the first kind. [Shai Covo (green355(AT)netvision.net.il), Jan 20 2010]
Jovovic's formula dated Sep 20 2006 can be restated as follows: a(n) is the n-th ascending factorial moment of the Poisson distribution with parameter (mean) 1. [Shai Covo (green355(AT)netvision.net.il), Jan 25 2010]
a(n) = n!* A067764(n) / A067653(n) [From Gary Detlefs, May 15 2010]
The umbral exponential generating function for a(n) is (1-x)^{-B}. In other words, write (1-x)^{-B} as a power series in x whose coefficients are polynomials in B, and then replace B^k with the Bell number B_k. We obtain a(0) + a(1)x + a(2)x^2/2! + ... . [From Richard Stanley, Jun 07 2010]
a(n) is the number of Dyck n-paths (A000108) with its peaks labelled 1,2,...,k in some order, where k is the number of peaks. For example a(2)=3 counts U(1)DU(2)D, U(2)DU(1)D, UU(1)DD where the label at each peak is in parentheses. This is easy to prove using generating functions. [David Callan, Aug 23 2011]
|
|
|
REFERENCES
|
Paul Barry, Combinatorial polynomials as moments, Hankel transforms and exponential Riordan arrays, Arxiv preprint arXiv:1105.3044, 2011
J.-P. Bultel, A, Chouria, J.-G. Luque and O. Mallet, Word symmetric functions and the Redfield-Polya theorem, 2013; http://hal.archives-ouvertes.fr/docs/00/79/37/88/PDF/Polya_arxiv.pdf
David Callan and Emeric Deutsch, The Run Transform, Arxiv preprint arXiv:1112.3639, 2011
Stefan Gerhold, Counting finite languages by total word length, INTEGERS 11 (2011), #A44; http://www.emis.de/journals/INTEGERS/papers/l44/l44.pdf.
D. E. Knuth, Convolution polynomials, The Mathematica J., 2 (1992), 67-78.
Laradji, A. and Umar, A. On the number of nilpotents in the partial symmetric semigroup. Comm. Algebra 32 (2004), 3017-3023. [From Abdullahi Umar, Sep 14 2008]
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176; the sequence called {!}^{n+}.
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 194.
Mark A. Shattuck and Carl G. Wagner, Parity Theorems for Statistics on Lattice Paths and Laguerre Configurations, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.1.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Y. Yakubovich, Ergodicity of multiplicative statistics, Journal of Combinatorial Theory, Series A 119 (2012) 1250-1279. - From N. J. A. Sloane, Sep 17 2012
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n = 0..100
P. Blasiak, A. Horzela, K. A. Penson, G.H.E. Duchamp and A. I. Solomon, Boson normal ordering via substitutions and Sheffer-type polynomials
P. Blasiak, K. A. Penson and A. I. Solomon, The Boson Normal Ordering Problem and Generalized Bell Numbers
P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem.
David Callan, Sets, Lists and Noncrossing Partitions .
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 125
F. Hivert, J.-C. Novelli and J.-Y. Thibon, Commutative combinatorial Hopf algebras
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 40
W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers (part 1)
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers (part 2)
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers (part 3)
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers (part 4)
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers (part 5)
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers (part 6)
K. A. Penson, P. Blasiak, G. Duchamp, A. Horzela and A. I. Solomon, Hierarchical Dobinski-type relations via substitution and the moment problem [J. Phys. A 37 (2004), 3475-3487]
N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 83-89.
Thomas Wieder, Further comments on this sequence
Index entries for "core" sequences
Index entries for sequences related to Laguerre polynomials
Index entries for related partition-counting sequences
|
|
|
FORMULA
|
a(n) = (2*n-1)*a(n-1) - (n-1)*(n-2)*a(n-2).
E.g.f.: exp( x/(1-x) ).
Representation as n-th moment of a positive function on positive half-axis, in Maple notation: a(n)=int(x^n*exp(-x-1)*BesselI(1, 2*x^(1/2))/x^(1/2), x =0..infinity), n=1, 2... - Karol A. Penson, Dec 4 2003.
a(n) = Sum_{k=0..n} A001263(n, k)*k!. - Philippe Deléham, Dec 10 2003
a(n) = n! Sum[Binomial[n-1, j]/(j+1)!, {j, 0, n-1}] for n=1, 2, 3, ... - Herbert S. Wilf (wilf(AT)math.upenn.edu), Jun 14 2005
Asymptotic expansion for large n: a(n)->(0.4289*n^(-1/4)+0.3574*n^(-3/4)-0.2531*n^(-5/4)+O(n^(-7/4)))*(n^n)*exp(-n+2*sqrt(n)) .- Karol A. Penson, Aug 28 2002
a(n) = exp(-1)*Sum_{m>=0} [m]^n/m!, where [m]^n = m*(m+1)*...*(m+n-1) is the rising factorial. - Vladeta Jovovic, Sep 20 2006
Recurrence: D(n,k) = D(n-1,k-1) + (n-1+k) * D(n-1,k) n >= k >= 0; D(n,0)=0. From this, D(n,1) = n! and D(n,n)=1; a(n) = sum(i=0..n, D(n,i) ). - Stephen Dalton (StephenMDalton(AT)gmail.com), Jan 05 2007
Proof: Notice two distinct subsets of the lists for [n]: 1) n is in its own list, then there are D(n-1,k-1); 2) n is in a list with other numbers. Denoting the separation of lists by |, it is not hard to see n has (n-1+k) possible positions, so (n-1+k) * D(n-1,k) - Stephen Dalton (StephenMDalton(AT)gmail.com), Jan 05 2007
Define f_1(x),f_2(x),... such that f_1(x)=exp(x), f_{n+1}(x)=diff(x^2*f_n(x),x), for n>=2. Then a(n-1)=exp(-1)*f_n(1). - Milan Janjic, May 30 2008
a(n) = (n-1)! * sum(k=1..n, (a(n-k)*k!)/((n-k)!*(k-1)!) ) where a(0)=1. [From Thomas Wieder, Sep 10 2008]
E.g.f. Q(0) where Q(k)=1+x/((1-x)*(2k+1)-x*(1-x)*(2k+1)/(x+(1-x)*(2k+2)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, Nov 17 2011
a(n) = D^n(exp(x)) evaluated at x = 0, where D is the operator (1+x)^2*d/dx. Cf. A000110, A049118, A049119 and A049120. - Peter Bala, Nov 25 2011
E.g.f. 1 + x/(G(0)-x) where G(k)= (1-x)*k + 1 - x*(1-x)*(k+1)/G(k+1); (continued fraction, Euler's 1st kind, 1-step). - Sergei N. Gladkovskii, Aug 02 2012
E.g.f.: exp(x/(1-x)) = 4/(2-(x/(1-x))*G(0))-1 where G(k) = 1 - x^2/(x^2 + 4*(1-x)^2*(2*k+1)*(2*k+3)/G(k+1) ); (recursively defined continued fraction). - Sergei N. Gladkovskii, Dec 11 2012
E.g.f.: 1 + x*(E(0)-1)/(x+1) where E(k) = 1 + 1/(k+1)/(1-x)/(1-x/(x+1/E(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Jan 27 2013
|
|
|
EXAMPLE
|
a(2) = 3: (12), (21), (1)(2). a(4) = 73: (1234) (24 ways), (123)(4) (6*4 ways), (12)(34) (3*4 ways), (12)(3)(4) (6*2 ways), (1)(2)(3)(4) (1 way).
a(2) = 3 from {1}{2}; {1,2}; {2,1}
1 + x + 3*x^2 + 13*x^3 + 73*x^4 + 501*x^4 + 4051*x^5 + 37633*x^6 + 394353*x^7 + ...
|
|
|
MAPLE
|
a := proc(n) option remember: if n=0 then RETURN(1) fi: if n=1 then RETURN(1) fi: (2*n-1)*a(n-1) - (n-1)*(n-2)*a(n-2) end:for n from 0 to 20 do printf(`%d, `, a(n)) od:
spec := [S, {S = Set(Prod(Z, Sequence(Z)))}, labeled]; [seq(combstruct[count](spec, size=n), n=0..40)];
with(combinat):seq(sum(abs(stirling1(n, k))*bell(k), k=0..n), n=0..18); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Nov 26 2006
B:=[S, {S = Set(Sequence(Z, 1 <= card), card <=13)}, labelled]: seq(combstruct[count](B, size=n), n=0..19); # [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Mar 21 2009]
|
|
|
MATHEMATICA
|
Range[0, 19]! CoefficientList[ Series[E^(x/(1 - x)), {x, 0, 19}], x] (from Robert G. Wilson v Apr 04 2005)
a[ n_] := If[ n<0, 0, n! SeriesCoefficient[ Exp[ x / (1 - x)], {x, 0, n}]]; Table[a[n], {n, 0, 20}] (* Michael Somos, Jul 19 2005 *)
a[n_]:=If[n==0, 1, n! Sum[Binomial[n-1, j]/(j+1)!, {j, 0, n-1}]]; Table[a[n], {n, 0, 30}] (Wilf)
a[0] = 1; a[n_] := n!*Hypergeometric1F1[n+1, 2, 1]/E; Table[a[n], {n, 0, 19}] (* Jean-François Alcover, Jun 18 2012, after Shai Covo *)
|
|
|
PROG
|
(PARI) {a(n) = if( n<0, 0, n! * polcoeff( exp( x / (1 - x) + x * O(x^n)), n))} /* Michael Somos, Feb 10 2005 */
(PARI) {a(n) = if( n<0, 0, n! * polcoeff( prod( k=1, n, eta(x^k + x * O(x^n))^( -moebius(k) / k)), n))} /* Michael Somos, Feb 10 2005 */
(Maxima) makelist(sum(abs(stirling1(n, k))*belln(k), k, 0, n), n, 0, 24); [Emanuele Munarini, Jul 4 2011]
|
|
|
CROSSREFS
|
a(n), n >= 1, is sum of n-th row of A008297 (unsigned Lah-triangle). [Wolfdieter Lang]
A002868 = maximal element of n-th row of A008297. Cf. A066668.
Cf. A001263.
A111596 (unsigned row sums of triangle).
Cf. A001700.
A052852 [From David Angell (angell(AT)maths.unsw.edu.au), Dec 18 2008]
Sequence in context: A193931 A193932 A193933 * A059294 A124468 A205572
Adjacent sequences: A000259 A000260 A000261 * A000263 A000264 A000265
|
|
|
KEYWORD
|
nonn,easy,core,nice,changed
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
More terms from James A. Sellers, Jul 06 2000
|
|
|
STATUS
|
approved
|
| |
|
|
