A370766 Number of signed permutations of length n with adjacent elements differing by more than 1.

1, 2, 4, 20, 156, 1540, 18268, 253380, 4024220, 72006788, 1433150940, 31402068292, 751081569820, 19471227247620, 543821277818972, 16278774958879940, 519912803924769948, 17646698226141369220, 634307673944308523740, 24070514898945667594308

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) = 4: 12(2), 21(2). Total is 2 + 2 = 4.
a(3) = 20: 123(2), 132(4), 213(4), 231(4), 312(4), 321(2).
		

Links

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

Crossrefs

Cf. A370767, A370768.

Programs

PARI

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

Formula

a(n) = A370767(n) + A370767(n-1) for n > 0.

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