%I A000085 M1221 N0469
%S A000085 1,1,2,4,10,26,76,232,764,2620,9496,35696,140152,568504,2390480,
%T A000085 10349536,46206736,211799312,997313824,4809701440,23758664096,
%U A000085 119952692896,618884638912,3257843882624,17492190577600,95680443760576
%N A000085 Number of self-inverse permutations on n letters, also known as involutions;
number of Young tableaux with n cells.
%C A000085 a(n) is also the number of n X n symmetric permutation matrices.
%C A000085 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
%C A000085 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
%C A000085 a(n) is the number of partitions of a set of n distinguishable elements
into sets of size 1 and 2. - Karol A. Penson (penson(AT)lptl.jussieu.fr),
Apr 22 2003.
%C A000085 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
%C A000085 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 (kolotoko(AT)wanadoo.fr), Jun 10 2005
%C A000085 Row sums of the exponential Riordan array (e^(x^2/2),x). - Paul Barry
(pbarry(AT)wit.ie), Jan 12 2006
%C A000085 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 (callan(AT)stat.wisc.edu),
Mar 07 2006
%C A000085 The descriptions in the Mathematica lines are due to w.meeussen (wouter.meeussen(AT)pandora.be).
%C A000085 Equals row sums of triangle A152736 starting with offset 1. [From Gary
W. Adamson (qntmpkt(AT)yahoo.com), Dec 12 2008]
%C A000085 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 (deutsch(AT)duke.poly.edu),
Jun 08 2009]
%C A000085 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"). [From
Joerg Arndt (arndt(AT)jjj.de), Jun 28 2009]
%D A000085 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 A000085 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 A000085 D. Castellanos, A generalization of Binet's formula and some of its consequences,
Fib. Quart., 27 (1989), 424-438.
%D A000085 C.-O. Chow, Counting involutory, unimodal and alternating signed permutations,
Discr. Math. 306 (2006), 2222-2228.
%D A000085 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.
%D A000085 S. Chowla, I. N. Herstein and W. K. Moore, On recursions connected with
symmetric groups I, Canad. J. Math., 3 (1951), 328-334.
%D A000085 R. Donaghey, Binomial self-inverse sequences and tangent coefficients,
J. Combin. Theory, Series A, 21 (1976), 155-163.
%D A000085 S. Dulucq and J.-G. Penaud, Cordes, arbres et permutations. Discrete
Math. 117 (1993), no. 1-3, 89-105.
%D A000085 W. Fulton, Young Tableaux, Cambridge, 1997.
%D A000085 J. Gilder, Rooks inviolate revisited II, Math. Gaz., 70 (1986), 44-45.
%D A000085 H. Gupta, Enumeration of symmetric matrices, Duke Math. J., 35 (1968),
653-659.
%D A000085 L. C. Larson, The number of essentially different nonattacking rook arrangements,
J. Recreat. Math., 7 (No. 3, 1974), circa pages 180-181.
%D A000085 L. Moser and M. Wyman, On solutions of x^d = 1 in symmetric groups, Canad.
J. Math., 7 (1955), 159-168.
%D A000085 T. Mueller, Finite group actions and asymptotic expansion of e^P(z),
Combinatorica, 17 (4) (1997), 523-554.
%D A000085 T. Muir, A Treatise on the Theory of Determinants. Dover, NY, 1960, p.
6.
%D A000085 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p.
86.
%D A000085 R. W. Robinson, Counting arrangements of bishops, pp. 198-214 of Combinatorial
Mathematics IV (Adelaide 1975), Lect. Notes Math., 560 (1976). See
D_n.
%D A000085 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973
(includes this sequence).
%D A000085 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences,
Academic Press, 1995 (includes this sequence).
%D A000085 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see
Example 5.2.10.
%H A000085 T. D. Noe, <a href="b000085.txt">Table of n, a(n) for n = 0..100</a>
%H A000085 David Applegate and N. J. A. Sloane, <a href="http://arxiv.org/abs/0907.0513">
The Gift Exchange Problem</a> (arXiv:0907.0513, 2009)
%H A000085 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Fxtbook</a>
%H A000085 E. A. Bender and S. G. Williamson, <a href="http://www.math.ucsd.edu/
~ebender/CombText/index.html">Foundations of Combinatorics with Applications</
a> (see Chap. 2, Example 2.9, pp. 47-48, including Theorem 2.2, a
derived formula for a(n)). [From Rick L. Shepherd (rshepherd2(AT)hotmail.com),
Sep 02 2009]
%H A000085 P. Blasiak, K. A. Penson, A. I. Solomon, A. Horzela and G. E. H. Duchamp,
<a href="http://arXiv.org/abs/quant-ph/0405103">Combinatorial field
theories via boson normal ordering</a>
%H A000085 D. Barsky, <a href="http://www.mat.univie.ac.at/~slc/opapers/s05barsky.html">
Analyse p-adique et suites classiques de nombres</a>, Sem. Loth.
Comb. B05b (1981) 1-21.
%H A000085 C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, <a href="http:/
/arXiv.org/abs/math.CO/0506334">On the x-rays of permutations</a>
%H A000085 P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
Sequences realized by oligomorphic permutation groups</a>, J. Integ.
Seqs. Vol. 3 (2000), #00.1.5.
%H A000085 A. M. Goyt, <a href="http://arXiv.org/abs/math.CO/0603481">Avoidance
of partitions of a 3-element set</a>
%H A000085 A. Horzela, P. Blasiak, G. E. H. Duchamp, K. A. Penson and A. I. Solomon,
<a href="http://arXiv.org/abs/quant-ph/0409152">A product formula
and combinatorial field theory</a>
%H A000085 INRIA Algorithms Project, <a href="http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=17">
Encyclopedia of Combinatorial Structures 17</a>
%H A000085 INRIA Algorithms Project, <a href="http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=22">
Encyclopedia of Combinatorial Structures 22</a>
%H A000085 W. Lang, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
On generalizations of Stirling number triangles</a>, J. Integer Seqs.,
Vol. 3 (2000), #00.2.4.
%H A000085 J. W. Layman, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
The Hankel Transform and Some of its Properties</a>, J. Integer Sequences,
4 (2001), #01.1.5.
%H A000085 E. Lucas, <a href="http://gallica.bnf.fr/scripts/ConsultationTout.exe?E=0&O=N029021">
Th\'{e}orie des Nombres</a>. Gauthier-Villars, Paris, 1891, Vol.
1, p. 221.
%H A000085 A. I. Solomon, P. Blasiak, G. Duchamp, A. Horzela and K. A. Penson, <a
href="http://arXiv.org/abs/quant-ph/0310174">Combinatorial physics,
normal order and model Feynman graphs</a>.
%H A000085 R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers/comb.ps">
A combinatorial miscellany</a>
%H A000085 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
PermutationInvolution.html">Link to a section of The World of Mathematics.</
a>
%H A000085 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
YoungTableau.html">Link to a section of The World of Mathematics.</
a>
%H A000085 <a href="Sindx_Cor.html#core">Index entries for "core" sequences</a>
%H A000085 <a href="Sindx_Y.html#Young">Index entries for sequences related to Young
tableaux.</a>
%H A000085 <a href="Sindx_Par.html#partN">Index entries for related partition-counting
sequences</a>
%F A000085 a(n) = a(n-1)+A013989(n-2) = A013989(n)/(n+1).
%F A000085 E.g.f.: exp(x+x^2/2). a(n) = a(n-1) + (n-1)*a(n-2), n>0. a(n)=Sum_{k=0..[
n/2 ]} n!/((n-2*k)!*2^k*k!).
%F A000085 a(m+n) = Sum_{k>=0} k!*binomial(m, k)*binomial(n, k)*a(m-k)*a(n-k) .
- DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Mar 05 2004
%F A000085 The e.g.f. y(x) satisfies y^2 = y''y' - (y')^2.
%F A000085 a(n) ~ c*(n/e)^(n/2)exp(n^(1/2)) where c=2^(-1/2)exp(-1/4). [Chowla]
%F A000085 Special values of Hermite polynomials. In Maple notation a(n)=HermiteH(n,
1/(sqrt(2)*I))/(-sqrt(2)*I)^n, n=0, 1..., from K. A. Penson (penson(AT)lptl.jussieu.fr),
May 16, 2002.
%F A000085 a(n)=sum{k=0..n, A001498((n+k)/2, (n-k)/2)(1+(-1)^(n-k))/2}; - Paul Barry
(pbarry(AT)wit.ie), Jan 12 2006
%F A000085 For asymptotics see the Robinson paper.
%F A000085 a[n]=Sum[A0099174[n,m],{m,0,n}]. - Roger Bagula (rlbagulatftn(AT)yahoo.com),
Oct 06 2006
%F A000085 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 (pauldhanna(AT)juno.com),
Jan 17 2006
%F A000085 Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 29 2008:
(Start)
%F A000085 a(n) = (n-1)*a(n-2) + a(n-1); e.g. a(7) = 232 = 6*26 + 76.
%F A000085 Starting with offset 1 = eigsensequence of triangle A128229. (End)
%e A000085 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 (se16(AT)btinternet.com),
Jan 16 2001
%p A000085 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;
%p A000085 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
%p A000085 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
%t A000085 Sum[ (2k)!/k!/2^k Binomial[ n, 2k ], {k, 0, n/2} ]//FullSimplify
%t A000085 HypergeometricU[ -(n/2), 1/2, -(1/2) ] / (-(1/2))^(-(-n/2))
%t A000085 NumberOfTableaux[M[Star[n]]]
%t A000085 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 (rlbagulatftn(AT)yahoo.com),
Oct 06 2006
%o A000085 (PARI) a(n)=if(n<0,0,n!*polcoeff(exp(x+x^2/2+x*O(x^n)),n))
%Y A000085 Cf. A001470, A047884, A049403, A099174, A136281-A136283.
%Y A000085 See also A005425 for another version of the switchboard problem.
%Y A000085 Equals 2 * A001475(n-1) for n>1.
%Y A000085 First column of array A099020.
%Y A000085 A069943(n+1)/A069944(n+1) = a(n)/A000142(n) in lowest terms.
%Y A000085 Row sums of array A117506 (M_4 numbers).
%Y A000085 A152736 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 12 2008]
%Y A000085 A128229 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 29 2008]
%Y A000085 Sequence in context: A007123 A007578 A007580 this_sequence A047653 A148100
A149815
%Y A000085 Adjacent sequences: A000082 A000083 A000084 this_sequence A000086 A000087
A000088
%K A000085 nonn,core,easy,nice
%O A000085 0,3
%A A000085 N. J. A. Sloane (njas(AT)research.att.com) and J. H. Conway (conway(AT)math.princeton.edu)
|
