This site is supported by donations to The OEIS Foundation.



The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000085 Number of self-inverse permutations on n letters, also known as involutions; number of Young tableaux with n cells.
(Formerly M1221 N0469)
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)



Getu (1991) says these numbers are also known as "telephone numbers". - N. J. A. Sloane, Nov 23 2015

a(n) is also the number of n X n symmetric permutation matrices.

a(n) is also the number of matchings (Hosoya index) in the complete graph K(n). - Ola Veshta (olaveshta(AT)my-deja.com), Mar 25 2001.

a(n) is also the number of independent vertex sets and vertex covers in the n-triangular graph. - Eric W. Weisstein, May 22 2017

Equivalently, this is the number of graphs on n labeled nodes with degrees at most 1. - Don 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, 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 Deléham, 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. - 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). - 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

Also called restricted Stirling numbers of the second kind (see Mezo). - N. J. A. Sloane, Nov 27 2013

a(n) = number of permutations of [n] that avoid the consecutive patterns 123 and 132. Proof. Write a self-inverse permutation in standard cycle form: smallest entry in each cycle in first position, first entries decreasing. For example, (6,7)(3,4)(2)(1,5) is in standard cycle form. Then erase parentheses. This is a bijection to the permutations that avoid consecutive 123 and 132 patterns. - David Callan, Aug 27 2014


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.

W. Fulton, Young Tableaux, Cambridge, 1997.

D. E. Knuth, The Art of Computer Programming, Vol. 3, Section 5.1.4, p. 65.

L. C. Larson, The number of essentially different nonattacking rook arrangements, J. Recreat. Math., 7 (No. 3, 1974), circa pages 180-181.

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.

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.


Alois P. Heinz, Table of n, a(n) for n = 0..800 (first 101 terms from T. D. Noe)

T. Amdeberhan, V. H. Moll, Involutions and their progenies, 2014.

David Applegate and N. J. A. Sloane, The Gift Exchange Problem arXiv:0907.0513 [math.CO], 2009.

Joerg Arndt, Generating Random Permutations, PhD thesis, Australian National University, Camberra, Australia, (2010).

Joerg Arndt, Matters Computational (The Fxtbook), pp. 279-280.

C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, Generating Functions for Generating Trees, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.

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]

S. Bilotta, E. Pergola, R. Pinzani, S. Rinaldi, Recurrence relations versus succession rules, arXiv preprint arXiv:1301.2967 [cs.DM], 2013. - From N. J. A. Sloane, Feb 12 2013

S. Bilotta, E. Pergola, R. Pinzani, S. Rinaldi, Recurrence Relations, Succession Rules, and the Positivity Problem, in Language and Automata Theory and Applications, 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings, Pages 499-510, Lecture Notes Comp. Sci. Vol. 8977.

P. Blasiak, K. A. Penson, A. I. Solomon, A. Horzela and G. E. H. Duchamp, Combinatorial field theories via boson normal ordering, arXiv:quant-ph/0405103, 2004-2006.

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

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, arXiv:math/0506334 [math.CO], 2005.

D. Bundala, M. Codish, L. Cruz-Filipe et al., Optimal-Depth Sorting Networks, arXiv preprint arXiv:1412.5302 [cs.DS], 2014.

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

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, and I.N. Hernstein, W.K. Moore, On recursions connected with symmetric groups. I, Canadian Journal of Mathematics, 3 (1951), 328-334.

M. Codish, L. Cruz-Filipe, P. Schneider-Kamp, The Quest for Optimal Sorting Networks: Efficient Generation of Two-Layer Prefixes, arXiv preprint arXiv:1404.0948 [cs.DS], 2014.

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 [math.CO], 2012.

I. Dolinka, J. East, A. Evangelou, D. FitzGerald, N. Ham, et al., Enumeration of idempotents in diagram semigroups and algebras, arXiv preprint arXiv:1408.2021 [math.GR], 2014.

I Dolinka, J East, RD Gray, Motzkin monoids and partial Brauer monoids, arXiv preprint arXiv:1512.02279, 2015

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.

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

FindStat - Combinatorial Statistic Finder, Standard Young tableaux

Mohammad Ganjtabesh, Armin Morabbi and Jean-Marc Steyaert, Enumerating the number of RNA structures

S. Garrabrant, I. Pak, Counting with irrational tiles, arXiv:1407.8222[math.CO], 2014.

S. Getu, Evaluating determinants via generating functions, Mathematics Magazine 64 (1991), 45-53.

J. Gilder, Rooks inviolate revisited II, Math. Gaz., 70 (1986), 44-45.

A. M. Goyt, Avoidance of partitions of a 3-element set, arXiv:math/0603481 [math.CO], 2006.

H. Gupta, Enumeration of symmetric matrices, Duke Math. J., 35 (1968), vol 3, 653-659

H. Gupta, >Enumeration of symmetric matrices (annotated scanned copy)

T. Halverson and M. Reeks, Gelfand Models for Diagram Algebras, arXiv preprint arXiv:1302.6150 [math.RT], 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.

A. Horzela, P. Blasiak, G. E. H. Duchamp, K. A. Penson and A. I. Solomon, A product formula and combinatorial field theory, arXiv:quant-ph/0409152, 2004.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 17

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 22

V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 227.

M. B. Kutler, C. R. Vinroot, On q-Analogs of Recursions for the Number of Involutions and Prime Order Elements in Symmetric Groups, JIS 13 (2010) #10.3.6.

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

L. C. Larson, The number of essentially different nonattacking rook arrangements, J. Recreat. Math., 7 (No. 3, 1974), circa pages 180-181. [Annotated scan of pages 180 and 181 only]

J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.

Steven Linton, James Propp, Tom Roby, Julian West, Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions, Journal of Integer Sequences, Vol. 15 (2012), #12.9.1.

E. Lucas, Théorie des Nombres. Gauthier-Villars, Paris, 1891, Vol. 1, p. 221.

E. Lucas, Théorie des nombres (annotated scans of a few selected pages)

T. Mansour and M. Shattuck, Partial matchings and pattern avoidance, Appl. Anal. Discrete Math. (to appear, 2012); - From N. J. A. Sloane, Jan 04 2013

I. Mezo, Periodicity of the last digits of some combinatorial sequences, arXiv preprint arXiv:1308.1637 [math.CO], 2013.

F. L. Miksa, L. Moser and M. Wyman, Restricted partitions of finite sets, Canad. Math. Bull., 1 (1958), 87-96.

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.

I. Pak, G. Panova, E. Vallejo, Kronecker products, characters, partitions, and the tensor square conjectures, arXiv:1304.0738 [math.CO], 2013.

D. Panyushev, On the orbits of a Borel subgroup in abelian ideals, arXiv preprint arXiv:1407.6857 [math.AG], 2014.

P. Peart and W.-J. Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.1.

R. A. Proctor, Let's Expand Rota's Twelvefold Way for Counting Partitions!, arXiv:math/0606404 [math.CO], 2006-2007.

J. L. Ramírez, G. N. Rubiano, Properties and Generalizations of the Fibonacci Word Fractal, The Mathematica Journal, Vol. 16 (2014).

J. Riordan, Letter to N. J. A. Sloane, Feb 03 1975 (with notes by njas)

R. W. Robinson, Counting arrangements of bishops, Lect. Notes Math. 560 (1976), 198-214. See D_n.

H. A. Rothe, Ueber Permutationen, in Beziehung auf die Stellen ihrer Elemente. Anwendung der daraus abgeleiteten Sätze auf das Eliminationsproblem, in Carl Hindenberg, ed., Sammlung Combinatorisch-Analytischer Abhandlungen, pp. 263-305, Bey G. Fleischer dem jüngern, 1800; see p. 282.

A. I. Solomon, P. Blasiak, G. Duchamp, A. Horzela and K. A. Penson, Combinatorial physics, normal order and model Feynman graphs, arXiv:quant-ph/0310174, 2003.

R. P. Stanley, A combinatorial miscellany

Robert F. Tichy and Stephan Wagner, Extremal Problems for Topological Indices in Combinatorial Chemistry, Journal of Computational Biology. September 2005, 12(7): 1004-1013.

Eric Weisstein's World of Mathematics, Complete Graph

Eric Weisstein's World of Mathematics, Hosoya Index

Eric Weisstein's World of Mathematics, Independent Edge Set

Eric Weisstein's World of Mathematics, Independent Vertex Set

Eric Weisstein's World of Mathematics, Matching

Eric Weisstein's World of Mathematics, Permutation Involution

Eric Weisstein's World of Mathematics, Triangular Graph

Eric Weisstein's World of Mathematics, Vertex Cover

Eric Weisstein's World of Mathematics, Young Tableau

Wikipedia, Telephone numbers.

Wikipedia, Young tableau.

Index entries for "core" sequences

Index entries for sequences related to Young tableaux.

Index entries for related partition-counting sequences


a(n) = a(n-1)+A013989(n-2) = A013989(n)/(n+1) = 1+A001189(n).

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

For n>1, a(n) = 2*(A000900(n)+A000902(floor(n/2))). - Max Alekseyev, Oct 31 2015

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

G.f.: - 1/(x*Q(0)), where Q(k) = 1 - 1/x - (k+1)/Q(k+1) ; (continued fraction). - Sergei N. Gladkovskii, Sep 15 2013

G.f.: T(0)/(1-x), where T(k) = 1 - x^2*(k+1)/( x^2*(k+1) - (1-x)^2/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 28 2013

a(n) ~ sqrt(2)/2 * exp(sqrt(n)-n/2-1/4) * n^(n/2) * (1 + 7/(24*sqrt(n))). - Vaclav Kotesovec, Mar 07 2014

a(n) = sum(s(n,k)*(-1)^(n-k)*2^k*B(k,1/2),k=0..n), where the s(n,k) are (signless) Stirling numbers of the first kind, and the B(n,x) = sum(S(n,k)*x^k,k=0..n) are the Stirling polynomials, where the S(n,k) are the Stirling numbers of the second kind. - Emanuele Munarini, May 16 2014

a(n) = hyper2F0([-n/2,(1-n)/2],[],2). - Peter Luschny, Aug 21 2014

0 = a(n)*(+a(n+1) + a(n+2) - a(n+3)) + a(n+1)*(-a(n+1) + a(n+2)) for all n in Z. - Michael Somos, Aug 22 2014


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

G.f. = 1 + x + 2*x^2 + 4*x^4 + 10*x^5 + 26*x^6 + 76*x^7 + 232*x^8 + 764*x^9 + ...


A000085 := proc(n) option remember; if n=0 then 1 elif n=1 then 1 else procname(n-1)+(n-1)*procname(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, 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, Jun 11 2008


<<Combinatorica`; 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 L. Bagula, Oct 06 2006

With[{nn=30}, CoefficientList[Series[Exp[x+x^2/2], {x, 0, nn}], x] Range[0, nn]!] (* Harvey P. Dale, May 28 2013 *)

a[ n_] := Sum[(2 k - 1)!! Binomial[ n, 2 k], {k, 0, n/2}]; (* Michael Somos, Jun 01 2013 *)

a[ n_] := If[ n < 0, 0, HypergeometricU[ -n/2, 1/2, -1/2] / (-1/2)^(n/2)]; (* Michael Somos, Jun 01 2013 *)

a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ Exp[ x + x^2 / 2], {x, 0, n}]]; (* Michael Somos, Jun 01 2013 *)

Table[(I/Sqrt[2])^n HermiteH[n, -I/Sqrt[2]], {n, 0, 100}] (* Emanuele Munarini, Mar 02 2016 *)


(PARI) {a(n) = if( n<0, 0, n! * polcoeff( exp( x + x^2 / 2 + x * O(x^n)), n))}; /* Michael Somos, Nov 15 2002 */


N=66;  x='x+O('x^N);

egf=exp(x+x^2/2);  Vec(serlaplace(egf))

/* Joerg Arndt, Mar 07 2013 */


a000085 n = a000085_list !! n

a000085_list = 1 : 1 : zipWith (+)

   (zipWith (*) [1..] a000085_list) (tail a000085_list)

-- Reinhard Zumkeller, May 16 2013

(Maxima) B(n, x):=sum(stirling2(n, k)*x^k, k, 0, n);

a(n):=sum(stirling1(n, k)*2^k*B(k, 1/2), k, 0, n);

makelist(a(n), n, 0, 40); /* Emanuele Munarini, May 16 2014 */


A000085 = lambda n: hypergeometric([-n/2, (1-n)/2], [], 2)

[round(A000085(n).n()) for n in range(28)] # Peter Luschny, Aug 21 2014

(Maxima) makelist((%i/sqrt(2))^n*hermite(n, -%i/sqrt(2)), n, 0, 12); /* Emanuele Munarini, Mar 02 2016 */


Cf. A001147, A001470, A047884, A049403, A099174, A136281-A136283, A001680, A001681.

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. - Gary W. Adamson, Dec 12 2008

Diagonal of A182172. - Alois P. Heinz, May 30 2012

Sequence in context: A239082 A229053 A229068 * A222319 A047653 A148100

Adjacent sequences:  A000082 A000083 A000084 * A000086 A000087 A000088




N. J. A. Sloane and J. H. Conway



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

License Agreements, Terms of Use, Privacy Policy .

Last modified May 27 02:10 EDT 2017. Contains 287189 sequences.