login
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.
4

%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