|
Search: id:A001540
|
|
|
| A001540 |
|
Number of transpositions needed to generate permutations of length n.
(Formerly M1856 N0734)
|
|
+0
2
|
|
| 0, 2, 8, 36, 184, 1110, 7776, 62216, 559952, 5599530, 61594840, 739138092, 9608795208, 134523132926, 2017846993904, 32285551902480, 548854382342176, 9879378882159186, 187708198761024552, 3754163975220491060
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
REFERENCES
|
R. J. Ord-Smith, Generation of permutation sequences: Part 1, Computer J., 13 (1970), 151-155.
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=1..100
|
|
FORMULA
|
E.g.f.: cosh(x)/(1-x) - exp(x).
Recurrence: a(n) = n*a(n-1) + n - (n mod 2).
a(n) = -1 + n!*sum{k=0, [n/2], 1/(2k)!} = -1 + round(n! * cosh(1)).
|
|
EXAMPLE
|
a(5)=-1+5!(1+1/2!+1/4!)=-1+120+60+5=184.
|
|
PROGRAM
|
(PARI) a(n)=-1+n!*sum(k=0, floor(n/2), 1/(2*k)!)
|
|
CROSSREFS
|
a(n) = |A009179(n)|-1 = (n-1)*|A009179(n-1)-A009179(n-2)|.
Sequence in context: A113327 A129148 A081958 this_sequence A129044 A052582 A020021
Adjacent sequences: A001537 A001538 A001539 this_sequence A001541 A001542 A001543
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
njas
|
|
EXTENSIONS
|
Edited by Ralf Stephan, Apr 16 2004
|
|
|
Search completed in 0.002 seconds
|
