A384921 Number of permutations [p_1, p_2, ..., p_n], for n >= 1, with |p_{i+1} - p_i| >= 2, for i = 1..n-1, and |p_n - p_1| = 0 or 1.

1, 0, 0, 2, 4, 30, 184, 1322, 10668, 96566, 969280, 10690146, 128527348, 1673257262, 23451539784, 352079626010, 5637207651004, 95886993887142, 1726775043225808, 32821564079286866, 656647922936247300, 13793480376190668446

Offset: 1

Author

Wolfdieter Lang, Jun 17 2025

Keywords

• nonn
• easy

Comments

This sequence gives the number of the so-called king permutations, for n >= 1, counted in A002464, that satisfy the additional restriction |p_n - p_1| = 0 or 1.

Examples

			n=1: The permutation is [1].
n=4: The two king permutations are [2, 4, 1, 3] and its reversal [3, 1, 4, 2].
n=5: The four permutations are [2,,4, 1, 5, 3], [3, 1, 5, 2, 4] and their reversals [3, 5, 1, 4, 2], [4, 2, 5, 1, 3]. See III of the Abramson and Moser link, p. 1254.
n=6: The 30 permutations are (in short cut version): 146352, 153642, 246153, 251463, 264153, 315264, 351624, 352614, 361524, 362514, 413625, 426135, 426315, 524136, 531426, and their reversals.
		

Links

• M. Abramson and W. O. J. Moser, Permutations without rising or falling w-sequences, Ann. Math. Stat., 38 (1967), 1245-1254, p. 1254, III.

Crossrefs

Cf. A002464, A002493.

Formula

a(n) = A002464(n) - A002493(n), for n >= 2, but A002493(1) = 1, not 0, as it is here, if instead of A002493 the definition |p_{i+1} - p_i| >= 2, for i = 1..n, for n >= 1, and p_{n+1} = p_1 is used; hence a(1) = 1, not 0.

a(n) = 2*Sum_{k=0..floor((n-2)/2)} A002464(n - (2*k+1)), for n >= 3, and a(1) = 1, a(2) = 0. (Compare this with the formula given by Vladeta Jovovic in A002493, Nov 24 2007.)