cp's OEIS Frontend

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.

%I A384921 #8 Jun 23 2025 21:52:40
%S A384921 1,0,0,2,4,30,184,1322,10668,96566,969280,10690146,128527348,
%T A384921 1673257262,23451539784,352079626010,5637207651004,95886993887142,
%U A384921 1726775043225808,32821564079286866,656647922936247300,13793480376190668446
%N 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.
%C A384921 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.
%H A384921 M. Abramson and W. O. J. Moser, <a href="http://dx.doi.org/10.1214/aoms/1177698793">Permutations without rising or falling w-sequences</a>, Ann. Math. Stat., 38 (1967), 1245-1254, p. 1254, III.
%F A384921 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.
%F A384921 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.)
%e A384921 n=1: The permutation is [1].
%e A384921 n=4: The two king permutations are [2, 4, 1, 3] and its reversal [3, 1, 4, 2].
%e A384921 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.
%e A384921 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.
%Y A384921 Cf. A002464, A002493.
%K A384921 nonn,easy
%O A384921 1,4
%A A384921 _Wolfdieter Lang_, Jun 17 2025