|
| |
|
|
A000085
|
|
Number of self-inverse permutations on n letters, also known as involutions; number of Young tableaux with n cells.
(Formerly M1221 N0469)
|
|
179
|
|
|
|
1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, 211799312, 997313824, 4809701440, 23758664096, 119952692896, 618884638912, 3257843882624, 17492190577600, 95680443760576, 532985208200576, 3020676745975552
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
a(n) is also the number of n X n symmetric permutation matrices.
a(n) is also the number of matchings in the complete graph K(n). - Ola Veshta (olaveshta(AT)my-deja.com), Mar 25 2001. Equivalently, this is the number of graphs on n labeled nodes with degrees at most 1. - _D. E. Knuth_, Mar 31 2008
a(n) is also the sum of the degrees of the irreducible representations of the symmetric group S_n - Avi Peretz (njk(AT)netvision.net.il), Apr 01 2001
a(n) is the number of partitions of a set of n distinguishable elements into sets of size 1 and 2. - Karol A. Penson, Apr 22 2003.
Number of tableaux on the edges of the star graph of order n, S_n (sometimes T_n) - Roberto E. Martinez II (remartin(AT)fas.harvard.edu), Jan 09 2002
The Hankel transform of this sequence is A000178 (superfactorials). Sequence is also binomial transform of the sequence 1, 0, 1, 0, 3, 0, 15, 0, 105, 0, 945, . . . (A001147 with interpolated zeros) . - Philippe DELEHAM, Jun 10 2005
Row sums of the exponential Riordan array (e^(x^2/2),x). - Paul Barry, Jan 12 2006
a(n) = number of nonnegative lattice paths of upsteps U = (1,1) and downsteps D = (1,-1) that start at the origin and end on the vertical line x = n in which each downstep (if any) is marked with an integer between 1 and the height of its initial vertex above the x-axis. For example, with the required integer immediately preceding each downstep, a(3) = 4 counts UUU, UU1D, UU2D, U1DU. - David Callan, Mar 07 2006
Equals row sums of triangle A152736 starting with offset 1. [From Gary W. Adamson, Dec 12 2008]
Proof of the recurrence relation a(n)=a(n-1)+(n-1)*a(n-2): number of involutions of [n] containing n as a fixed point is a(n-1); number of involutions of [n] containing n in some cycle (j, n), where 1<=j<=n-1, is (n-1) times the number of involutions of [n] containing the cycle (n-1 n) = (n-1)*a(n-2). [From Emeric Deutsch, Jun 08 2009]
Number of ballot sequences (or lattice permutations) of length n. A ballot sequence B is a string such that, for all prefixes P of B, h(i)>=h(j) for i<j, where h(x) is the number of times x appears in P. For example, the ballot sequences of length 4 are 1111, 1112, 1121, 1122, 1123, 1211, 1212, 1213, 1231, and 1234. The string 1221 does not appear in the list because in the 3-prefix 122 there are two 2s but only one 1. (Cf. p.176 of Bruce E. Sagan: "The Symmetric Group"). [Joerg Arndt, Jun 28 2009]
Number of standard Young tableaux of size n; the ballot sequences are obtained as a length-n vector v where v_k is the (number of the) row in which the number r occurs in the tableaux. [Joerg Arndt, Jul 29 2012]
Number of factorial numbers of length n-1 with no adjacent nonzero digits. For example the 10 such numbers (in rising factorial radix) of length 3 are 000, 001, 002, 003, 010, 020, 100, 101, 102, and 103. [Joerg Arndt, Nov 11 2012]
|
|
|
REFERENCES
|
C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, [http://algo.inria.fr/banderier/Papers/DiscMath99.ps Generating Functions for Generating Trees], Discrete Mathematics 246(1-3), March 2002, pp. 29-55.
S. Bilotta, E. Pergola, R. Pinzani, S. Rinaldi, Recurrence relations versus succession rules, arXiv preprint arXiv:1301.2967, 2013. - From N. J. A. Sloane, Feb 12 2013
P. Blasiak, K. A. Penson, A. I. Solomon, A. Horzela and G. E. H. Duchamp, Some useful combinatorial formulas for bosonic operators, J. Math. Phys. 46, 052110 (2005) (6 pages).
P. Blasiak, K. A. Penson, A. I. Solomon, A. Horzela and G. E. H. Duchamp, Combinatorial field theories via boson normal ordering, preprint, Apr 27 2004.
D. Castellanos, A generalization of Binet's formula and some of its consequences, Fib. Quart., 27 (1989), 424-438.
C.-O. Chow, Counting involutory, unimodal and alternating signed permutations, Discr. Math. 306 (2006), 2222-2228.
S. Chowla, The asymptotic behavior of solutions of difference equations, in Proceedings of the International Congress of Mathematicians (Cambridge, MA, 1950), Vol. I, 377, Amer. Math. Soc., Providence, RI, 1952.
S. Chowla, I. N. Herstein and W. K. Moore, On recursions connected with symmetric groups I, Canad. J. Math., 3 (1951), 328-334.
R. Donaghey, Binomial self-inverse sequences and tangent coefficients, J. Combin. Theory, Series A, 21 (1976), 155-163.
S. Dulucq and J.-G. Penaud, Cordes, arbres et permutations. Discrete Math. 117 (1993), no. 1-3, 89-105.
W. Fulton, Young Tableaux, Cambridge, 1997.
J. Gilder, Rooks inviolate revisited II, Math. Gaz., 70 (1986), 44-45.
H. Gupta, Enumeration of symmetric matrices, Duke Math. J., 35 (1968), 653-659.
T. Halverson and M. Reeks, Gelfand Models for Diagram Algebras, arXiv preprint arXiv:1302.6150, 2013
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011; http://repository.wit.ie/1693/1/AoifeThesis.pdf
D. E. Knuth, The Art of Computer Programming, Vol. 3, Section 5.1.4, p. 65. [From N. J. A. Sloane, May 05 2011]
L. C. Larson, The number of essentially different nonattacking rook arrangements, J. Recreat. Math., 7 (No. 3, 1974), circa pages 180-181.
T. Mansour and M. Shattuck, Partial matchings and pattern avoidance, Appl. Anal. Discrete Math. (to appear, 2012); DOI: 10.2298/AADM121130023M. - From N. J. A. Sloane, Jan 04 2013
L. Moser and M. Wyman, On solutions of x^d = 1 in symmetric groups, Canad. J. Math., 7 (1955), 159-168.
T. Mueller, Finite group actions and asymptotic expansion of e^P(z), Combinatorica, 17 (4) (1997), 523-554.
T. Muir, A Treatise on the Theory of Determinants. Dover, NY, 1960, p. 6.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 86.
R. W. Robinson, Counting arrangements of bishops, pp. 198-214 of Combinatorial Mathematics IV (Adelaide 1975), Lect. Notes Math., 560 (1976). See D_n.
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).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.10.
Robert F. Tichy and Stephan Wagner, Extremal Problems for Topological Indices in Combinatorial Chemistry, Journal of Computational Biology. September 2005, 12(7): 1004-1013. doi:10.1089/cmb.2005.12.1004.
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n = 0..100
David Applegate and N. J. A. Sloane, The Gift Exchange Problem (arXiv:0907.0513, 2009)
Joerg Arndt, Fxtbook, pp.279-280
E. A. Bender and S. G. Williamson, Foundations of Combinatorics with Applications (see Chap. 2, Example 2.9, pp. 47-48, including Theorem 2.2, a derived formula for a(n)). [From Rick L. Shepherd, Sep 02 2009]
P. Blasiak, K. A. Penson, A. I. Solomon, A. Horzela and G. E. H. Duchamp, Combinatorial field theories via boson normal ordering
D. Barsky, Analyse p-adique et suites classiques de nombres, Sem. Loth. Comb. B05b (1981) 1-21.
C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, On the x-rays of permutations
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
T. Copeland, Infinitesimal Generators, the Pascal Pyramid, and the Witt and Virasoro Algebras
Filippo Disanto and Thomas Wiehe, Some instances of a sub-permutation problem on pattern avoiding permutations, arXiv preprint arXiv:1210.6908, 2012.
Shalosh B. Ekhad and Doron Zeilberger, Computational and Theoretical Challenges on Counting Solid Standard Young Tableaux. Also Arxiv preprint arXiv:1202.6229, 2012. - N. J. A. Sloane, Jul 07 2012
Mohammad GANJTABESH, Armin MORABBI and Jean-Marc STEYAERT, Enumerating the number of RNA structures
A. M. Goyt, Avoidance of partitions of a 3-element set
A. Horzela, P. Blasiak, G. E. H. Duchamp, K. A. Penson and A. I. Solomon, A product formula and combinatorial field theory
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 17
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 22
W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
E. Lucas, Th\'{e}orie des Nombres. Gauthier-Villars, Paris, 1891, Vol. 1, p. 221.
A. I. Solomon, P. Blasiak, G. Duchamp, A. Horzela and K. A. Penson, Combinatorial physics, normal order and model Feynman graphs.
R. P. Stanley, A combinatorial miscellany
Eric Weisstein's World of Mathematics, Permutation Involution
Eric Weisstein's World of Mathematics, Young Tableau
Wikipedia, Young tableau.
Index entries for "core" sequences
Index entries for sequences related to Young tableaux.
Index entries for related partition-counting sequences
|
|
|
FORMULA
|
a(n) = a(n-1)+A013989(n-2) = A013989(n)/(n+1).
E.g.f.: exp(x+x^2/2).
a(n) = a(n-1) + (n-1)*a(n-2), n>1.
a(n)=Sum_{k=0..[ n/2 ]} n!/((n-2*k)!*2^k*k!).
a(m+n) = Sum_{k>=0} k!*binomial(m, k)*binomial(n, k)*a(m-k)*a(n-k) . - Philippe Deléham, Mar 05 2004
The e.g.f. y(x) satisfies y^2 = y''y' - (y')^2.
a(n) ~ c*(n/e)^(n/2)exp(n^(1/2)) where c=2^(-1/2)exp(-1/4). [Chowla]
Special values of Hermite polynomials. In Maple notation a(n)=HermiteH(n, 1/(sqrt(2)*I))/(-sqrt(2)*I)^n, n=0, 1..., - Karol A. Penson, May 16, 2002.
a(n) = sum{k=0..n, A001498((n+k)/2, (n-k)/2)(1+(-1)^(n-k))/2}; - Paul Barry, Jan 12 2006
For asymptotics see the Robinson paper.
a(n) = Sum_{m=0..n} A099174(n,m). - Roger Bagula, Oct 06 2006
O.g.f.: A(x) = 1/(1-x-1*x^2/(1-x-2*x^2/(1-x-3*x^2/(1-... -x-n*x^2/(1- ...))))) (continued fraction). - Paul D. Hanna, Jan 17 2006
From Gary W. Adamson, Dec 29 2008: (Start)
a(n) = (n-1)*a(n-2) + a(n-1); e.g. a(7) = 232 = 6*26 + 76.
Starting with offset 1 = eigsensequence of triangle A128229. (End)
a(n) = (1/sqrt(2*Pi))*int(exp(-x^2/2)*(x+1)^(n),x=-infinity..infinity) - Groux Roland, Mar 14 2011.
E.g.f.: 1+x*(2+x)/(2*G(0)-x*(2+x)) where G(k)=1+x*(x+2)/(2+2*(k+1)/G(k+1)); (continued fraction). - Sergei N. Gladkovskii, Dec 03 2011
Row sums of |A096713|. a(n) = D^n(exp(x)) evaluated at x = 0, where D is the operator sqrt(1+2*x)*d/dx. Cf. A047974 and A080599. - Peter Bala, Dec 07 2011
G.f.: 1/(U(0) - x) where U(k)= 1 + x*(k+1) - x*(k+1)/(1 - x/U(k+1)) ; (continued fraction, 2-step). - Sergei N. Gladkovskii, Oct 12 2012
G.f.: 1/Q(0) where Q(k) = 1 + x*k - x/(1 - x*(k+1)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Mar 06 2013
|
|
|
EXAMPLE
|
Sequence starts 1, 1, 2, 4, 10, ... because possibilities are: {}, {A}, {AB, BA}, {ABC, ACB, BAC, CBA}, {ABCD, ABDC, ACBD, ADCB, BACD, BADC, CBAD, CDAB, DBCA, DCBA} - Henry Bottomley, Jan 16 2001
|
|
|
MAPLE
|
A000085 := proc(n) option remember; if n=0 then 1 elif n=1 then 1 else A000085(n-1)+(n-1)*A000085(n-2); fi; end;
with(combstruct):ZL3:=[S, {S=Set(Cycle(Z, card<3))}, labeled]:seq(count(ZL3, size=n), n=0..25); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Sep 24 2007
with (combstruct):a:=proc(m) [ZL, {ZL=Set(Cycle(Z, m>=card))}, labeled]; end: A:=a(2):seq(count(A, size=n), n=0..25); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 11 2008
|
|
|
MATHEMATICA
|
Sum[ (2k)!/k!/2^k Binomial[ n, 2k ], {k, 0, n/2} ]//FullSimplify
HypergeometricU[ -(n/2), 1/2, -(1/2) ] / (-(1/2))^(-(-n/2))
NumberOfTableaux[M[Star[n]]]
p[0, x] = 1; p[1, x] = x; p[k_, x_] := p[k, x] = x*p[k - 1, x] + (k - 1)*p[k - 2, x]; Table[Sum[CoefficientList[p[n, x], x][[m]], {m, 1, n + 1}], {n, 0, 15}] - Roger Bagula, Oct 06 2006
|
|
|
PROG
|
(PARI) a(n)=if(n<0, 0, n!*polcoeff(exp(x+x^2/2+x*O(x^n)), n))
(PARI)
N=66; x='x+O('x^N);
egf=exp(x+x^2/2); Vec(serlaplace(egf))
/* Joerg Arndt, Mar 07 2013 */
(Haskell)
a000085 n = a000085_list !! n
a000085_list = 1 : 1 : zipWith (+)
(zipWith (*) [1..] a000085_list) (tail a000085_list)
-- Reinhard Zumkeller, May 16 2013
|
|
|
CROSSREFS
|
Cf. A001147 (the number of fixed-point-free involutions).
Cf. A001147, A001470, A047884, A049403, A099174, A136281-A136283.
See also A005425 for another version of the switchboard problem.
Equals 2 * A001475(n-1) for n>1.
First column of array A099020.
A069943(n+1)/A069944(n+1) = a(n)/A000142(n) in lowest terms.
Row sums of array A117506 (M_4 numbers).
Cf. A152736, A128229. [From Gary W. Adamson, Dec 12 2008]
Diagonal of A182172. - Alois P. Heinz, May 30 2012
Sequence in context: A007580 A212915 A212916 * A222319 A047653 A148100
Adjacent sequences: A000082 A000083 A000084 * A000086 A000087 A000088
|
|
|
KEYWORD
|
nonn,core,easy,nice,changed
|
|
|
AUTHOR
|
N. J. A. Sloane and J. H. Conway (conway(AT)math.princeton.edu)
|
|
|
STATUS
|
approved
|
| |
|
|
