A370768 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.

1, 1, 5, 29, 249, 2553, 31181, 441845, 7133569, 129304593, 2600559125, 57473713741, 1384615153033, 36115750475433, 1014026439534045, 30493381288216357, 977824818833573137, 33307253433327375809, 1201023016203128722725, 45705676512051750367357

Offset

0,3

Comments

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}.

Adjacent elements that differ in sign will always differ by more than 1.

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.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..200

Formula

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.

Example

In the following examples, the number of assignments of signs to each unsigned permutation is shown in parenthesis.
a(0) = 1 from the signed permutation (1, -2).
a(1) = 1 from the signed permutation (1, -2, 3).
a(2) = 5: 1234(1), 1324(4). Total is 1 + 4 = 5.
a(3) = 29: 12345(1), 12435(4), 13245(4), 13425(8), 14235(8), 14325(4).
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).

Prog

(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)

Crossrefs

Cf. A370766, A370767.

Sequence in context: A000354 A103815 A134752 * A231712 A215867 A342423

Adjacent sequences: A370765 A370766 A370767 * A370769 A370770 A370771

Keyword

nonn

Author

Andrew Howroyd, Mar 01 2024

Status

approved