login
A259834
Number of permutations of [n] with no fixed points where the maximal displacement of an element equals n-1.
5
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,4
COMMENTS
a(n) counts permutations p of [n] such that p(i) <> i and (p(1) = n or p(n) = 1).
LINKS
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
EXAMPLE
a(2) = 1: 21.
a(3) = 2: 231, 312.
a(4) = 5: 2341, 3421, 4123, 4312, 4321.
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 *)
PROG
(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
CROSSREFS
A diagonal of A259784.
Sequence in context: A347071 A214816 A020005 * A074415 A020001 A348597
KEYWORD
nonn,easy
AUTHOR
Alois P. Heinz, Jul 06 2015
STATUS
approved