OFFSET
0,5
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..893
FORMULA
a(n) = Sum_{j=1..floor(n/2)} binomial(n-j-1, j-1)*(d(j) + d(j-1)), where d(i) = A000166(i) are the derangement numbers; a(0)=1.
EXAMPLE
a(5)=3 because we have 12345, 34512, and 45123.
MAPLE
d[ -1] := 0: d[0] := 1: for n to 50 do d[n] := n*d[n-1]+(-1)^n end do: a := proc (n) options operator, arrow: sum(binomial(n-j-1, j-1)*(d[j]+d[j-1]), j = 1 .. floor((1/2)*n)) end proc:a(0):=1: seq(a(n), n = 0 .. 32);
# second Maple program:
a:= proc(n) option remember; `if`(n<4, [1, 0, 1, 1][n+1],
(3*a(n-1)+(n-3)*a(n-2)-(n-3)*a(n-3)+(n-4)*a(n-4))/2)
end:
seq(a(n), n=0..31); # Alois P. Heinz, Feb 17 2024
MATHEMATICA
a[n_] := If[n == 0, 1, With[{d = Subfactorial}, Sum[Binomial[n-j-1, j-1]* (d[j] + d[j-1]), {j, 1, Floor[n/2]}]]];
Table[a[n], {n, 0, 31}] (* Jean-François Alcover, Sep 17 2024 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Sep 09 2010
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Feb 17 2024
STATUS
approved