A000266 - OEIS

%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