A370767 Number of signed permutations of length n+1 with adjacent elements differing by more than 1 and whose first element is 1.

1, 1, 3, 17, 139, 1401, 16867, 236513, 3787707, 68219081, 1364931859, 30037136433, 721044433387, 18750182814233, 525071095004739, 15753703863875201, 504159100060894747, 17142539126080474473, 617165134818228049267, 23453349764127439545041

Offset: 0

Author

Andrew Howroyd, Mar 01 2024

Keywords

• nonn

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.

Examples

			In the following examples, the number of assignments of signs to each unsigned permutation is shown in parenthesis.
a(2) = 3: 123(1), 132(2). Total is 1 + 2 = 3.
a(3) = 17: 1234(1), 1243(2), 1324(4), 1342(4), 1423(4), 1432(2).
		

Links

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

Crossrefs

Cf. A283184, A370766, A370768.

Programs

PARI

a(n)=subst(serlaplace(polcoef(1/(1 + (1 - 2*y)*x + 2*y*x^2) + O(x*x^n), n)), y, 1)

Formula

A283184(n) = a(n) - a(n-1) for n > 0.

a(n) = (1+2*n)*a(n-1) + (3-2*n)*a(n-2) + (5-2*n)*a(n-3) + (-4+2*n)*a(n-4) for n >= 4.