A161132 - OEIS

%I #36 Jul 26 2022 16:13:05

%S 1,1,1,4,14,78,426,3216,24024,229080,2170680,25022880,287250480,

%T 3884393520,52370755920,812752093440,12585067447680,220448163358080,

%U 3854801333416320,75225258805132800,1465957162768492800,31537353006189676800,677696237345719468800

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

%H Alois P. Heinz, <a href="/A161132/b161132.txt">Table of n, a(n) for n = 0..450</a>

%F 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.

%F a(n) = Sum_{j=0..floor(n/2)} (-1)^j*binomial(floor(n/2),j)*(n-j)!.

%F a(n) = A267383(n,ceiling(n/2)). - _Alois P. Heinz_, Jan 13 2016

%F a(n) ~ exp(-1/2) * n!. - _Vaclav Kotesovec_, Feb 18 2017

%F From _Mark van Hoeij_, Jul 15 2022: (Start)

%F a(2*n) = A033815(n),

%F a(2*n+1) = (A033815(n) + A033815(n+1)/(n+1))/2. (End)

%F From _Peter Luschny_, Jul 15 2022: (Start)

%F a(n) = n!*hypergeom([-floor(n/2)], [-n], -1).

%F a(n) = A068106(n, ceiling(n/2)). (End)

%F 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

%e a(3)=4 because we have 132, 312, 213, and 231.

%p 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);

%p 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

%p a := n -> n!*hypergeom([-floor(n/2)], [-n], -1):

%p seq(simplify(a(n)), n = 0..22);  # _Peter Luschny_, Jul 15 2022

%t 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 *)

%o (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

%o (Python)

%o import math

%o f=math.factorial

%o def C(n, r): return f(n)/ f(r)/ f(n - r)

%o def A161132(n):

%o     s=0

%o     for j in range(0, (n/2)+1):

%o         s += (-1)**j*C(n/2, j)*f(n - j)

%o     return s # _Indranil Ghosh_, Mar 08 2017

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

%K nonn

%O 0,4

%A _Emeric Deutsch_, Jul 18 2009