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

Author

Seiichi Manyama, Jun 22 2018

Keywords

• nonn

Examples

			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               |
		

Links

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

Crossrefs

Cf. A000166, A000313, A065087, A090672.

Programs

PARI

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

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