login
Number of transpositions needed to generate permutations of length n.
(Formerly M1856 N0734)
2

%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