Logo

Greetings from The On-Line Encyclopedia of Integer Sequences!

Hints

Search: id:A000262
Displaying 1-1 of 1 results found. page 1
     Format: long | short | internal | text      Sort: relevance | references | number      Highlight: on | off
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)
+0
85
1, 1, 3, 13, 73, 501, 4051, 37633, 394353, 4596553, 58941091, 824073141, 12470162233, 202976401213, 3535017524403, 65573803186921, 1290434218669921, 26846616451246353, 588633468315403843, 13564373693588558173 (list; graph; listen)
OFFSET

0,3

COMMENT

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 (vladeta(AT)Eunet.yu), Jan 19 2003

a(n) = Sum_{k=0..n} |A008275(n,k)| * A000110(k). - Vladeta Jovovic (vladeta(AT)Eunet.yu), Feb 01 2003

a(n) = (n-1)!*LaguerreL(n-1,1,-1). - Vladeta Jovovic (vladeta(AT)Eunet.yu), 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 (wieder.thomas(AT)t-online.de), 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 (thomas.wieder(AT)t-online.de), 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 (dwalsh(AT)mtsu.edu), 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 (tcjpn(AT)msn.com), 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 (thomas.wieder(AT)t-online.de), May 25 2008

REFERENCES

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

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.

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.

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

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)=(2n-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, penson(AT)lptl.jussieu.fr Dec 4 2003.

a(n) = Sum_{k=0..n} A001263(n, k)*k!. - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), 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 (penson(AT)lptl.jussieu.fr), 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 (vladeta(AT)Eunet.yu), 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[from i=0 to 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)=e^x, f_{n+1}(x)=diff(x^2*f_n(x),x), for n=2,3,.... Then a(n-1)=e^{-1}*f_n(1). - Milan R. Janjic (agnus(AT)blic.net), May 30 2008

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}

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

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[Series[Exp[x/(1-x)], {x, 0, n}], n]] (Somos)

a[n_]:=If[n=0, 1, n! Sum[Binomial[n-1, j]/(j+1)!, {j, 0, n-1}]] (Wilf)

PROGRAM

(PARI) a(n)=if(n<0, 0, n!*polcoeff(exp(x/(1-x)+x*O(x^n)), n))

(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 */

CROSSREFS

a(n), n >= 1, is sum of n-th row of A008297 (unsigned Lah-triangle) - comment from Wolfdieter Lang (wolfdieter.lang(AT)physik.uni-karlsruhe.de)

A002868 = maximal element of n-th row of A008297. Cf. A066668.

Cf. A001263.

A111596 (unsigned row sums of triangle).

Cf. A001700.

Sequence in context: A067764 A063512 A132846 this_sequence A059294 A124468 A128196

Adjacent sequences: A000259 A000260 A000261 this_sequence A000263 A000264 A000265

KEYWORD

nonn,easy,core,nice

AUTHOR

njas

EXTENSIONS

More terms from James A. Sellers (sellersj(AT)math.psu.edu), Jul 06 2000

page 1

Search completed in 0.004 seconds

Lookup | Welcome | Find friends | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Puzzles | Hot | Classics
More pages | Superseeker | Maintained by N. J. A. Sloane (njas@research.att.com)

Last modified July 25 07:41 EDT 2008. Contains 142293 sequences.


AT&T Labs Research