login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)
108
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. - Giuliano Cabrele (giulianocabrele(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). - Abdullahi Umar, Sep 14 2008

A000262 is the exp transform of the factorial numbers A000142. - 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). - 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! + ... . - Richard Stanley, Jun 07 2010

a(n) is the number of Dyck n-paths (A000108) with its peaks labeled 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

a(n) = number of permutations of the multiset {1,1,2,2,...,n,n} such that for 1<=i<=n, all entries between the two i's exceed i and if any such entries are present, they include n. There are (2n-1)!! permutations satisfying the first condition, and for example: a(3)=13 counts all 5!!=15 of them except 331221 and 122133 which fail the second condition. - David Callan, Aug 27 2014_

REFERENCES

Salvador Jacobi, Planning in Multi-Agent Systems, Technical University of Denmark, Department of Applied Mathematics and Computer Science, 2800 Kongens Lyngby, Denmark, 2014; file:///Users/njasloane/Downloads/imm6799.pdf

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.

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).

LINKS

T. D. Noe, Table of n, a(n) for n = 0..100

A. Aboud, J.-P. Bultel, A. Chouria, J.-G. Luque, O. Mallet, Bell polynomials in combinatorial Hopf algebras, arXiv preprint arXiv:1402.2960, 2014

Paul Barry, Combinatorial polynomials as moments, Hankel transforms and exponential Riordan arrays, arXiv preprint arXiv:1105.3044, 2011

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.

J.-P. Bultel, A, Chouria, J.-G. Luque and O. Mallet, Word symmetric functions and the Redfield-Polya theorem, 2013;

David Callan, Sets, Lists and Noncrossing Partitions , arXiv:0711.4841 [math.CO].

David Callan and Emeric Deutsch, The Run Transform,  Discrete Math. 312 (2012), no. 19, 2927-2937, arXiv:1112.3639, 2011

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

Stefan Gerhold, Counting finite languages by total word length, INTEGERS 11 (2011), #A44.

F. Hivert, J.-C. Novelli and J.-Y. Thibon, Commutative combinatorial Hopf algebras

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 40

D. E. Knuth, Convolution polynomials, The Mathematica J., 2 (1992), 67-78.

W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.

A. Laradji and A. Umar, On the number of nilpotents in the partial symmetric semigroup, Comm. Algebra 32 (2004), 3017-3023.

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]

Robert A. Proctor, Let's Expand Rota's Twelvefold Way For Counting Partitions!, arXiv:math.CO/0606404, Jan 05, 2007

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.

M. Shattuck, Combinatorial proofs of some Bell number formulas, arXiv preprint arXiv:1401.6588, 2014

N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 83-89.

Thomas Wieder, Further comments on this sequence

Y. Yakubovich, Ergodicity of multiplicative statistics, Journal of Combinatorial Theory, Series A 119 (2012) 1250-1279, alternative copy.

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 04 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

Minor part of this asymptotic expansion is wrong! Right is (in closed form): a(n) ~ n^(n-1/4)*exp(-1/2+2*sqrt(n)-n)/sqrt(2) * (1 - 5/(48*sqrt(n)) - 95/(4608*n)), numerically a(n) ~ (0.42888194248*n^(-1/4) - 0.0446752023417*n^(-3/4) - 0.00884196713*n^(-5/4) + O(n^(-7/4))) *(n^n)*exp(-n+2*sqrt(n)). - Vaclav Kotesovec, Jun 02 2013

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. - 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) ); (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) )); (continued fraction). - Sergei N. Gladkovskii, Jan 27 2013

E.g.f.: E(0)/2, where E(k)= 1 + 1/(1 - x/(x + (k+1)*(1-x)/E(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 31 2013

E.g.f.: E(0)-1, where E(k) = 2 + x/( (2*k+1)*(1-x) - x/E(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Dec 25 2013

E.g.f.: product {n >= 1} ( (1 + x^n)/(1 - x^n) )^( phi(2*n)/(2*n) ), where phi(n) = A000010(n) is the Euler totient function. Cf. A088009. - Peter Bala, Jan 01 2014

a(n) = n!*hypergeom([1-n],[2],-1) for n>=1. - Peter Luschny, Jun 05 2014

a(n) = (-1)^(n-1)*KummerU(1-n,2,-1). - Peter Luschny, Sep 17 2014

a(n) = hypergeom([-n+1, -n, -n], [-n], 1) for n>=0. - Peter Luschny, Oct 17 2014

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}

G.f. = 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, Nov 26 2006

B:=[S, {S = Set(Sequence(Z, 1 <= card), card <=13)}, labelled]: seq(combstruct[count](B, size=n), n=0..19); # Zerinvary Lajos, Mar 21 2009

a := n -> n!*hypergeom([1 - n], [2], -1): seq(round(evalf(a(n), 32)), n=0..19); # Peter Luschny, Jun 05 2014

MATHEMATICA

Range[0, 19]! CoefficientList[ Series[E^(x/(1 - x)), {x, 0, 19}], x] (* Robert G. Wilson v, Apr 04 2005 *)

a[ n_] := If[ n<0, 0, n! SeriesCoefficient[ Exp[ x / (1 - x)], {x, 0, n}]]; (* 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 04 2011 */

(Haskell)

a000262 n = a000262_list !! n

a000262_list = 1 : 1 : zipWith (-)

               (tail $ zipWith (*) a005408_list a000262_list)

                      (zipWith (*) a002378_list a000262_list)

-- Reinhard Zumkeller, Mar 06 2014

(Sage)

A000262 = lambda n: hypergeometric([-n+1, -n, -n], [-n], 1)

[simplify(A000262(n)) for n in (0..19)] # Peter Luschny, Oct 17 2014

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. - David Angell (angell(AT)maths.unsw.edu.au), Dec 18 2008

Cf. A005408, A002378.

Sequence in context: A193931 A193932 A193933 * A059294 A124468 A205572

Adjacent sequences:  A000259 A000260 A000261 * A000263 A000264 A000265

KEYWORD

nonn,easy,core,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from James A. Sellers, Jul 06 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified November 24 02:09 EST 2014. Contains 249867 sequences.