login
A161132
Number of permutations of {1,2,...,n} that have no even fixed points.
6
1, 1, 1, 4, 14, 78, 426, 3216, 24024, 229080, 2170680, 25022880, 287250480, 3884393520, 52370755920, 812752093440, 12585067447680, 220448163358080, 3854801333416320, 75225258805132800, 1465957162768492800, 31537353006189676800, 677696237345719468800
OFFSET
0,4
LINKS
FORMULA
a(n) = Sum_{j=0..ceiling(n/2)} d(n-j)*binomial(ceiling(n/2), j), where d(i) = A000166(i) are the derangement numbers.
a(n) = Sum_{j=0..floor(n/2)} (-1)^j*binomial(floor(n/2),j)*(n-j)!.
a(n) = A267383(n,ceiling(n/2)). - Alois P. Heinz, Jan 13 2016
a(n) ~ exp(-1/2) * n!. - Vaclav Kotesovec, Feb 18 2017
From Mark van Hoeij, Jul 15 2022: (Start)
a(2*n) = A033815(n),
a(2*n+1) = (A033815(n) + A033815(n+1)/(n+1))/2. (End)
From Peter Luschny, Jul 15 2022: (Start)
a(n) = n!*hypergeom([-floor(n/2)], [-n], -1).
a(n) = A068106(n, ceiling(n/2)). (End)
D-finite with recurrence +16*a(n) -24*a(n-1) +4*(-4*n^2+8*n+3)*a(n-2) +4*(2*n^2-10*n+9)*a(n-3) +2*(-4*n^2+22*n-31)*a(n-4) +2*(n-2)*(n-4)*a(n-5) -(n-4)*(n-5)*a(n-6)=0. - R. J. Mathar, Jul 26 2022
EXAMPLE
a(3)=4 because we have 132, 312, 213, and 231.
MAPLE
d[0] := 1: for n to 25 do d[n] := n*d[n-1]+(-1)^n end do: a := proc (n) options operator, arrow: add(d[n-j]*binomial(ceil((1/2)*n), j), j = 0 .. ceil((1/2)*n)) end proc: seq(a(n), n = 0 .. 22);
a := proc (n) options operator, arrow: add((-1)^j*binomial(floor((1/2)*n), j)*factorial(n-j), j = 0 .. floor((1/2)*n)) end proc; seq(a(n), n = 0 .. 22); # Emeric Deutsch, Jul 18 2009
a := n -> n!*hypergeom([-floor(n/2)], [-n], -1):
seq(simplify(a(n)), n = 0..22); # Peter Luschny, Jul 15 2022
MATHEMATICA
a[n_] := Sum[Subfactorial[n-j]*Binomial[Ceiling[n/2], j], {j, 0, Ceiling[ n/2]}]; Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Feb 19 2017 *)
PROG
(PARI)for (n=0, 30, print1(sum(j=0, floor(n/2), (-1)^j*binomial(floor(n/2), j)*(n - j)!), ", ")) \\ Indranil Ghosh, Mar 08 2017
(Python)
import math
f=math.factorial
def C(n, r): return f(n)/ f(r)/ f(n - r)
def A161132(n):
s=0
for j in range(0, (n/2)+1):
s += (-1)**j*C(n/2, j)*f(n - j)
return s # Indranil Ghosh, Mar 08 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Jul 18 2009
STATUS
approved