cp's OEIS Frontend

A161131 Number of permutations of {1,2,...,n} that have no odd fixed points.

%I A161131 #27 Apr 25 2024 09:09:56
%S A161131 1,0,1,3,14,64,426,2790,24024,205056,2170680,22852200,287250480,
%T A161131 3597143040,52370755920,760381337520,12585067447680,207863095910400,
%U A161131 3854801333416320,71370457471716480,1465957162768492800,30071395843421184000,677696237345719468800
%N A161131 Number of permutations of {1,2,...,n} that have no odd fixed points.
%H A161131 Alois P. Heinz, <a href="/A161131/b161131.txt">Table of n, a(n) for n = 0..450</a>
%F A161131 a(n) = Sum_{j=0..floor(n/2)} d(n-j)*binomial(floor(n/2), j), where d(i)=A000166(i) are the derangement numbers.
%F A161131 a(n) = Sum_{j=0..ceiling(n/2)} (-1)^j*binomial(ceiling(n/2), j)*(n-j)!. - _Emeric Deutsch_, Jul 18 2009
%F A161131 a(n) ~ exp(-1/2) * n!. - _Vaclav Kotesovec_, Feb 18 2017
%F A161131 From _Peter Luschny_, Jul 15 2022: (Start)
%F A161131 a(n) = n!*hypergeom([-ceiling(n/2)], [-n], -1).
%F A161131 a(n) = A068106(n, floor(n/2)). (End)
%F A161131 D-finite with recurrence +16*a(n) -24*a(n-1) -4*(2*n-1)*(2*n-3)*a(n-2) +4*(2*n^2-10*n+15)*a(n-3) +2*(-10*n+29)*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 A161131 a(3)=3 because we have 312, 231, and 321.
%p A161131 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(floor((1/2)*n), j), j = 0 .. floor((1/2)*n)) end proc; seq(a(n), n = 0 .. 22);
%p A161131 a := proc (n) options operator, arrow: add((-1)^j*binomial(ceil((1/2)*n), j)*factorial(n-j), j = 0 .. ceil((1/2)*n)) end proc; seq(a(n), n = 0 .. 22); # _Emeric Deutsch_, Jul 18 2009
%p A161131 # next Maple program:
%p A161131 a:= proc(n) option remember; `if`(n<4, [1, 0, 1, 3][n+1],
%p A161131       (8*(n-1)*(2*n-5)*a(n-1)+2*(8*n^4-48*n^3+102*n^2-90*n+29)*a(n-2)
%p A161131        -2*(2*n-1)*(n-2)*a(n-3)+(2*n-1)*(2*n-3)*(n-2)*(n-3)*a(n-4))
%p A161131        /(4*(2*n-3)*(2*n-5)))
%p A161131     end:
%p A161131 seq(a(n), n=0..30);  # _Alois P. Heinz_, Jul 15 2022
%p A161131 a := n -> n!*hypergeom([-ceil(n/2)], [-n], -1):
%p A161131 seq(simplify(a(n)), n = 0..22);  # _Peter Luschny_, Jul 15 2022
%t A161131 Table[Sum[(-1)^j*Binomial[Ceiling[n/2], j]*(n-j)!, {j, 0, Ceiling[n/2]}], {n, 0, 30}] (* _Vaclav Kotesovec_, Feb 18 2017 *)
%o A161131 (PARI) for(n=0, 30, print1(sum(j=0, ceil(n/2), (-1)^j*binomial(ceil(n/2), j)*(n - j)!),", ")) \\ _Indranil Ghosh_, Mar 08 2017
%Y A161131 Cf. A000166, A068106, A161132.
%K A161131 nonn
%O A161131 0,4
%A A161131 _Emeric Deutsch_, Jul 18 2009