OFFSET
1,4
COMMENTS
From Emeric Deutsch, Sep 07 2010: (Start)
a(n) is also the number of fixed points in all those permutations of [n-1] that have no adjacent fixed points. Example: a(4)=3 because in 132, 213, 231, 312, 321 we have 1+1+0+0+1 fixed points.
a(n) is also the number of permutations of [n] having exactly 1 pair of adjacent fixed points. Example: a(4)=3 because we have 1243, 4231, and 2134.
(End)
REFERENCES
Wayne M. Dymacek, Isaac Lambert and Kyle Parsons, Arithmetic Progressions in Permutations, http://math.ku.edu/~ilambert/CN.pdf, 2012. - From N. J. A. Sloane, Sep 15 2012
FORMULA
EXAMPLE
a(4)=3 because in 1*243, 1324, 13*42, 142*3, 1432 we have 3 successions (marked *).
MAPLE
d[0] := 1: for n to 51 do d[n] := n*d[n-1]+(-1)^n end do: seq(sum(k*binomial(n-k, k)*d[n-1-k], k = 0 .. floor((1/2)*n)), n = 1 .. 22);
MATHEMATICA
a[0] = 1; a[n_] := a[n] = n*a[n - 1] + (-1)^n; f[n_] := Sum[k*Binomial[n - k, k]*a[n - k - 1], {k, 0, n/2}]; Array[f, 21] (* Robert G. Wilson v, Apr 01 2011 *)
a[n_] := Sum[k Binomial[n - k, k] Subfactorial[n - k - 1], {k, 0, n/2}];
a /@ Range[1, 21] (* Jean-François Alcover, Oct 29 2019 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Sep 06 2010
STATUS
approved