%I M1856 N0734 #51 Sep 08 2022 08:44:29
%S 0,2,8,36,184,1110,7776,62216,559952,5599530,61594840,739138092,
%T 9608795208,134523132926,2017846993904,32285551902480,548854382342176,
%U 9879378882159186,187708198761024552,3754163975220491060,78837443479630312280,1734423756551866870182
%N Number of transpositions needed to generate permutations of length n.
%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).
%H Alois P. Heinz, <a href="/A001540/b001540.txt">Table of n, a(n) for n = 1..450</a> (first 100 terms from T. D. Noe)
%H R. J. Ord-Smith, <a href="https://doi.org/10.1093/comjnl/13.2.152">Generation of permutation sequences: Part 1</a>, Computer J., 13 (1970), 151-155.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%F E.g.f.: cosh(x)/(1-x) - exp(x).
%F Recurrence: a(n) = n*a(n-1) + n - (n mod 2).
%F a(n) = -1 + n!*Sum{k=0..floor(n/2)} 1/(2*k)! = -1 + round(n! * cosh(1)).
%F a(n) = |A009179(n)| - 1 = (n-1)*|A009179(n-1) - A009179(n-2)|.
%F a(n) ~ [cosh(1)*n!] - 1, where [x] is the floor of x. - _Simon Plouffe_, Nov 28 2018
%e a(5)=-1+5!(1+1/2!+1/4!)=-1+120+60+5=184.
%p a := n -> (exp(1)*GAMMA(1 + n, 1) + exp(-1)*GAMMA(1 + n, -1))/2 - 1:
%p seq(simplify(a(n)), n=1..20); # _Peter Luschny_, Dec 05 2018
%t With[{nn=20},Rest[CoefficientList[Series[Cosh[x]/(1-x)-Exp[x],{x,0,nn}],x]Range[0,nn]!]] (* _Harvey P. Dale_, Mar 04 2013 *)
%o (PARI) a(n)=-1+n!*sum(k=0,floor(n/2),1/(2*k)!)
%o (J) a001540=:13 : '<:+/(!y)%!+:i.>:<.-:y' NB. _Stephen Makdisi_, May 02 2018
%o (Magma) [-1 + (&+[Factorial(n)/Factorial(2*k): k in [0..Floor(n/2)]]): n in [1..20]]; // _G. C. Greubel_, Nov 28 2018
%o (Sage) [-1 + factorial(n)*sum(1/factorial(2*k) for k in range(floor((n+2)/2))) for n in (1..20)] # _G. C. Greubel_, Nov 28 2018
%o (GAP) a:=[0];; for n in [2..20] do a[n]:=n*a[n-1]+n-(n mod 2); od; a; # _Muniru A Asiru_, Dec 05 2018
%Y Cf. A009179.
%K nonn,easy,nice
%O 1,2
%A _N. J. A. Sloane_
%E Edited by _Ralf Stephan_, Apr 16 2004