A305730 a(n) is the total displacement of all letters in all permutations of n letters with no fixed points.

0, 0, 2, 8, 60, 440, 3710, 34608, 355992, 4004880, 48948570, 646121080, 9163171732, 138974771208, 2244977073430, 38485321258720, 697867158824880, 13346709412525728, 268504389357870642, 5668425997555046760, 125302048367006296940, 2894477317277845459160

Offset

0,3

Links

Seiichi Manyama, Table of n, a(n) for n = 0..400

Formula

a(n) = n * (n+1) * A000166(n)/3 = 2/3 * A065087(n).

a(n) = n * (n+1)!/3 * Sum_{k=0..n} (-1)^k/k!.

a(n) = n * (n+1) * (a(n-1)/(n-1) + (-1)^n/3) for n > 1.

a(n) = 2 * A000313(n+2). - Alois P. Heinz, Jun 22 2018

E.g.f.: exp(-x)*x^2*(3 - 2*x + x^2)/(3*(1 - x)^3). - Ilya Gutkovskiy, Jun 25 2018

Example

n | 1 2 3 4 | the displacement of all letters | a(n)
--+---------+---------------------------------+------
2 | 2 1     | 1 + 1 = 2                       |   2
3 | 2 3 1   | 1 + 1 + 2 = 4                   |   8
  | 3 1 2   | 2 + 1 + 1 = 4                   |
4 | 2 1 4 3 | 1 + 1 + 1 + 1 = 4               |  60
  | 2 3 4 1 | 1 + 1 + 1 + 3 = 6               |
  | 2 4 1 3 | 1 + 2 + 2 + 1 = 6               |
  | 3 1 4 2 | 2 + 1 + 1 + 2 = 6               |
  | 3 4 1 2 | 2 + 2 + 2 + 2 = 8               |
  | 3 4 2 1 | 2 + 2 + 1 + 3 = 8               |
  | 4 1 2 3 | 3 + 1 + 1 + 1 = 6               |
  | 4 3 1 2 | 3 + 1 + 2 + 2 = 8               |
  | 4 3 2 1 | 3 + 1 + 1 + 3 = 8               |

Prog

(PARI) {a(n) = n*(n+1)!/3*sum(k=0, n, (-1)^k/k!)}

Crossrefs

Cf. A000166, A000313, A065087, A090672.

Sequence in context: A196076 A027278 A001415 * A364077 A053871 A364395

Adjacent sequences: A305727 A305728 A305729 * A305731 A305732 A305733

Keyword

nonn

Author

Seiichi Manyama, Jun 22 2018

Status

approved