%I #13 Mar 06 2024 19:40:58
%S 1,1,5,29,249,2553,31181,441845,7133569,129304593,2600559125,
%T 57473713741,1384615153033,36115750475433,1014026439534045,
%U 30493381288216357,977824818833573137,33307253433327375809,1201023016203128722725,45705676512051750367357
%N Number of signed permutations of length n+2 with adjacent elements differing by more than 1 whose first element is 1 and whose last element has absolute value n+2.
%C A signed permutation is a sequence (x_1,x_2,...,x_n) of integers such that {|x_1|,|x_2|,...|x_n|} = {1,2...,n}.
%C Adjacent elements that differ in sign will always differ by more than 1.
%C a(n) is also half the number of signed permutations of length n+1 with adjacent elements differing by more than 1 whose first element has absolute value 1 or whose last element has absolute value n+1.
%H Andrew Howroyd, <a href="/A370768/b370768.txt">Table of n, a(n) for n = 0..200</a>
%F a(n) = 2*n*a(n-1) + 4*a(n-2) + 4*(2-n)*a(n-3) + a(n-4) - 2*(2-n)*a(n-5) for n >= 5.
%e In the following examples, the number of assignments of signs to each unsigned permutation is shown in parenthesis.
%e a(0) = 1 from the signed permutation (1, -2).
%e a(1) = 1 from the signed permutation (1, -2, 3).
%e a(2) = 5: 1234(1), 1324(4). Total is 1 + 4 = 5.
%e a(3) = 29: 12345(1), 12435(4), 13245(4), 13425(8), 14235(8), 14325(4).
%e The 2*a(3) = 58 signed permutations of length 4 with adjacent elements differing by more than 1 which start with +-1 or end with +-4 are: 1234(2), 1243(4), 1324(8), 1342(8), 1423(8), 1432(4), 2134(4), 2314(8), 3124(8), 3214(4).
%o (PARI) a(n)=subst(serlaplace(polcoef(2/((1 + x)*(1 + (1 - 2*y)*x + 2*y*x^2)) - 1/(1 + x) + O(x*x^n), n)), y, 1)
%Y Cf. A370766, A370767.
%K nonn
%O 0,3
%A _Andrew Howroyd_, Mar 01 2024