cp's OEIS Frontend

A296050 Number of permutations p of [n] such that min_{j=1..n} |p(j)-j| = 1.

%I A296050 #101 Aug 30 2021 09:39:39
%S A296050 0,0,1,2,8,40,236,1648,13125,117794,1175224,12903874,154615096,
%T A296050 2007498192,28075470833,420753819282,6726830163592,114278495205524,
%U A296050 2055782983578788,39039148388975552,780412763620655061,16381683795665956242,360258256118419518680,8283042472303599966974
%N A296050 Number of permutations p of [n] such that min_{j=1..n} |p(j)-j| = 1.
%H A296050 Alois P. Heinz, <a href="/A296050/b296050.txt">Table of n, a(n) for n = 0..450</a>
%F A296050 a(n) = A000142(n) - A001883(n) - A002467(n).
%F A296050 a(n) = A000166(n) - A001883(n).
%F A296050 a(n) = Sum_{k=1..n} A323671(n,k).
%F A296050 a(n) is odd <=> n in { A016933 }.
%F A296050 a(n) is even <=> n in { A047252 }.
%e A296050 a(2) = 1: 21.
%e A296050 a(3) = 2: 231, 312.
%e A296050 a(4) = 8: 2143, 2341, 2413, 3142, 3421, 4123, 4312, 4321.
%e A296050 a(5) = 40: 21453, 21534, 23154, 23451, 23514, 24153, 24513, 24531, 25134, 25413, 25431, 31254, 31452, 31524, 34152, 34251, 35124, 35214, 35412, 35421, 41253, 41523, 41532, 43152, 43251, 43512, 43521, 45132, 45213, 45231, 51234, 51423, 51432, 53124, 53214, 53412, 53421, 54132, 54213, 54231.
%p A296050 b:= proc(s, k) option remember; (n-> `if`(n=0, `if`(k=1, 1, 0), add(
%p A296050       `if`(n=j, 0, b(s minus {j}, min(k, abs(n-j)))), j=s)))(nops(s))
%p A296050     end:
%p A296050 a:= n-> b({$1..n}, n):
%p A296050 seq(a(n), n=0..14);
%p A296050 # second Maple program:
%p A296050 a:= n-> (f-> f(1)-f(2))(k-> `if`(n=0, 1, LinearAlgebra[Permanent](
%p A296050         Matrix(n, (i, j)-> `if`(abs(i-j)>=k, 1, 0))))):
%p A296050 seq(a(n), n=0..14);
%p A296050 # third Maple program:
%p A296050 g:= proc(n) g(n):= `if`(n<2, 1-n, (n-1)*(g(n-1)+g(n-2))) end:
%p A296050 h:= proc(n) h(n):= `if`(n<7, [1, 0$3, 1, 4, 29][n+1], n*h(n-1)+4*h(n-2)
%p A296050       -3*(n-3)*h(n-3)+(n-4)*h(n-4)+2*(n-5)*h(n-5)-(n-7)*h(n-6)-h(n-7))
%p A296050     end:
%p A296050 a:= n-> g(n)-h(n):
%p A296050 seq(a(n), n=0..25);
%t A296050 g[n_] := g[n] = If[n < 2, 1-n, (n-1)(g[n-1] + g[n-2])];
%t A296050 h[n_] := h[n] = If[n < 7, {1, 0, 0, 0, 1, 4, 29}[[n+1]],
%t A296050      n h[n-1] + 4h[n-2] - 3(n-3)h[n-3] + (n-4)h[n-4] +
%t A296050      2(n-5)h[n-5] - (n-7)h[n-6] - h[n-7]];
%t A296050 a[n_] := g[n] - h[n];
%t A296050 Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Aug 30 2021, after third Maple program *)
%Y A296050 Column k=1 of A299789.
%Y A296050 Cf. A000142, A000166, A001883, A002467, A016933, A047252, A323671.
%K A296050 nonn
%O A296050 0,4
%A A296050 _Alois P. Heinz_, Jan 21 2019