A161132 Number of permutations of {1,2,...,n} that have no even fixed points.

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

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

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

Cf. A000166, A033815, A068106, A161131, A267383.

Sequence in context: A009347 A341505 A231510 * A186638 A187847 A277039

Adjacent sequences: A161129 A161130 A161131 * A161133 A161134 A161135

Keyword

nonn

Author

Emeric Deutsch, Jul 18 2009

Status

approved