%I M2991 N1211 #75 Aug 06 2022 07:25:17
%S 1,1,1,3,15,75,435,3045,24465,220185,2200905,24209955,290529855,
%T 3776888115,52876298475,793144477125,12690313661025,215735332237425,
%U 3883235945814225,73781482970470275,1475629660064134575,30988222861346826075,681740902935880863075
%N Expansion of e.g.f. exp(-x^2/2) / (1-x).
%C a(n) is the number of permutations in the symmetric group S_n whose cycle decomposition contains no transposition.
%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 85.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D R. P. Stanley, Enumerative Combinatorics, Wadsworth, Vol. 1, 1986, page 93, problem 7.
%H Alois P. Heinz, <a href="/A000266/b000266.txt">Table of n, a(n) for n = 0..450</a> (first 101 terms from T. D. Noe)
%H Larry Carter and Stan Wagon, <a href="https://www.jstor.org/stable/48663293">The Mensa Correctional Institute</a>, The American Mathematical Monthly 125.4 (2018): 306-319.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=104">Encyclopedia of Combinatorial Structures 104</a>
%H Simon Plouffe, <a href="http://www.plouffe.fr/simon/exact.htm">Exact formulas for integer sequences</a>, March 1993.
%F E.g.f.: exp( x + Sum_{k>2} x^k / k ). - _Michael Somos_, Jul 25 2011
%F a(n) = n! * Sum_{i=0..floor(n/2)} (-1)^i /(i! * 2^i); a(n)/n! ~ Sum_{i>=0} (-1)^i /(i! * 2^i) = e^(-1/2); a(n) ~ e^(-1/2) * n!; a(n) ~ e^(-1/2) * (n/e)^n * sqrt(2*Pi*n). - Avi Peretz (njk(AT)netvision.net.il), Apr 21 2001
%F A027616(n) + a(n) = n!. - Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 09 2003
%F a(n) = n!*floor((floor(n/2)! * 2^floor(n/2) / exp(1/2) + 1/2)) / (floor(n/2)! * 2^floor(n/2)), n >= 0. - _Simon Plouffe_ from old notes, 1993
%F E.g.f.: 1/(1-x)*exp(-(x^2)/2) = 1/((1-x)*G(0)); G(k) = 1+(x^2)/(2*(2*k+1)-2*(x^2)*(2*k+1)/((x^2)+4*(k+1)/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Nov 24 2011
%F E.g.f.: 1/Q(0), where Q(k) = 1 - x/(1 - x/(x - (2*k+2)/Q(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, May 15 2013
%F D-finite with recurrence: a(n) - n*a(n-1) + (n-1)*a(n-2) - (n-1)*(n-2)*a(n-3) = 0. - _R. J. Mathar_, Feb 16 2020
%e a(3) = 3 because the permutations in S_3 that contain no transpositions are the trivial permutation and the two 3-cycles.
%p G:=exp(-z^2/2)/(1-z): Gser:=series(G,z=0,26): for n from 0 to 25 do a(n):=n!*coeff(Gser,z,n): end do: seq(a(n), n=0..20); # _Paul Weisenhorn_, May 29 2010
%p # second Maple program:
%p a:= proc(n) option remember; `if`(n=0, 1, add(
%p a(n-j)*(j-1)!*binomial(n-1, j-1), j=[1, $3..n]))
%p end:
%p seq(a(n), n=0..30); # _Alois P. Heinz_, May 12 2016
%t a=Log[1/(1-x)]-x^2/2; Range[0,20]! CoefficientList[Series[Exp[a], {x,0,20}], x] (* _Geoffrey Critzer_, Nov 29 2011 *)
%o (PARI) {a(n) = if( n<0, 0, n! * polcoeff( exp(-(x^2/2)+x*O(x^n)) / (1 - x), n))} /* _Michael Somos_, Jul 28 2009 */
%Y See also A000138 and A000090.
%Y Cf. A027616, A130905, A193385.
%K nonn
%O 0,4
%A _N. J. A. Sloane_
%E More terms from _Christian G. Bower_
%E Entry improved by comments from _Michael Somos_, Jul 28 2009
%E Minor editing by _Johannes W. Meijer_, Jul 25 2011