Search: id:A000085 Results 1-1 of 1 results found. %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 iTable of n, a(n) for n = 0..100 %H A000085 David Applegate and N. J. A. Sloane, The Gift Exchange Problem (arXiv:0907.0513, 2009) %H A000085 Joerg Arndt, Fxtbook %H A000085 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 (rshepherd2(AT)hotmail.com), Sep 02 2009] %H A000085 P. Blasiak, K. A. Penson, A. I. Solomon, A. Horzela and G. E. H. Duchamp, Combinatorial field theories via boson normal ordering %H A000085 D. Barsky, Analyse p-adique et suites classiques de nombres, Sem. Loth. Comb. B05b (1981) 1-21. %H A000085 C. Bebeacua, T. Mansour, A. Postnikov and S. Severini, On the x-rays of permutations %H A000085 P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5. %H A000085 A. M. Goyt, Avoidance of partitions of a 3-element set %H A000085 A. Horzela, P. Blasiak, G. E. H. Duchamp, K. A. Penson and A. I. Solomon, A product formula and combinatorial field theory %H A000085 INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 17 %H A000085 INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 22 %H A000085 W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4. %H A000085 J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5. %H A000085 E. Lucas, Th\'{e}orie des Nombres. Gauthier-Villars, Paris, 1891, Vol. 1, p. 221. %H A000085 A. I. Solomon, P. Blasiak, G. Duchamp, A. Horzela and K. A. Penson, Combinatorial physics, normal order and model Feynman graphs. %H A000085 R. P. Stanley, A combinatorial miscellany %H A000085 Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics. %H A000085 Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics. %H A000085 Index entries for "core" sequences %H A000085 Index entries for sequences related to Young tableaux. %H A000085 Index entries for related partition-counting sequences %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) Search completed in 0.003 seconds