A259834 Number of permutations of [n] with no fixed points where the maximal displacement of an element equals n-1.

0, 0, 1, 2, 5, 20, 97, 574, 3973, 31520, 281825, 2803418, 30704101, 367114252, 4757800705, 66432995030, 994204132517, 15875195019224, 269397248811073, 4841453414347570, 91856764780324165, 1834779993945449348, 38485629141294791201, 845788826477292504302

Offset: 0

Author

Alois P. Heinz, Jul 06 2015

Keywords

• nonn
• easy

Comments

a(n) counts permutations p of [n] such that p(i) <> i and (p(1) = n or p(n) = 1).

Examples

			a(2) = 1: 21.
a(3) = 2: 231, 312.
a(4) = 5: 2341, 3421, 4123, 4312, 4321.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..450

Crossrefs

A diagonal of A259784.

Cf. A000142, A000166, A000255, A292897, A292898, A306455.

Programs

Maple

a:= proc(n) option remember; `if`(n<3, [0, 0, 1][n+1],
     ((2*n^2-11*n+13)*a(n-1) +(2*n-5)*(n-3)*a(n-2))/(2*n-7))
    end:
seq(a(n), n=0..30);

Mathematica

Join[{0, 0}, Table[DifferenceRoot[Function[{y, m}, {y[1 + m] == (n - m)*y[m] + (n - m) y[m - 1], y[0] == 0, y[1] == 1, y[2] == 1}]][n], {n, 2, 30}]] (* Benedict W. J. Irwin, Nov 03 2016 *)
Table[If[n<2, 0, Subfactorial[n-2]+2*Subfactorial[n-1]], {n,0,23}] (* Peter Luschny, Oct 04 2017 *)

Python

def A259834_list(len):
    L, u, x, y = [0], 1, 0, 0
    for n in range(len):
        y, x, u = x, x*n + u, -u
        L.append(y + 2*x)
    L[1] = 0
    return L
print(A259834_list(23)) # Peter Luschny, Oct 04 2017

Formula

a(n) = ((2*n^2-11*n+13)*a(n-1) + (2*n-5)*(n-3)*a(n-2))/(2*n-7) for n > 2.

a(n) = (n-2)! * [x^(n-2)] exp(-x)*(x+1)/(x-1)^2 for n > 1.

a(n) ~ 2 * (n-1)! / exp(1). - Vaclav Kotesovec, Jul 07 2015

a(n) = y(n,n), n > 1, where y(m+1,n) = (n-m)*y(m,n) + (n-m)*y(m-1,n), with y(0,n)=0, y(1,n)=y(2,n)=1 for all n. - Benedict W. J. Irwin, Nov 03 2016

From Peter Luschny, Oct 05 2017: (Start)

a(n) = (Gamma(n-1, -1) + 2*Gamma(n, -1)) / e for n >= 2.

a(n) = A000166(n-2) + 2*A000166(n-1) for n >= 2.

a(n) = (2*n-1)*A000166(n-2) - 2*(-1)^n for n >= 2.

a(n) = A000255(n-2) + A000166(n-1) for n >= 2.

a(n+2) = (-1)^n*(-hypergeom([1,1-n], [], 1) + hypergeom([2,2-n], [], 1)) = A292898(2, n) for n >= 0.

a(n) ~ 2*sqrt(2*Pi)*exp(-n-1)*n^(n-1/2). (End)

a(n+2) = A306455(n) + n! for n >= 0. - Alois P. Heinz, Feb 16 2019