A384561 One fourth of the number of permutations of [n] with |p(i+1) - p(i)| >= 2, for i = 1..(n-1) and n appears at position i = 1 or i = n.

1, 6, 39, 284, 2337, 21474, 218179, 2430216, 29459301, 386182478, 5444570631, 82157021556, 1321282006249, 22562446559034, 407722012334667, 7773697259015264, 155956589714240109, 3284208113313605286, 72434065593967762831, 1669777527837108720588, 40157785493048522566641

Offset: 5

Author

Wolfdieter Lang, Jun 04 2025

Keywords

• nonn
• easy

Comments

The number of such permutations of [n] is 1 for n = 1 (the p(i) condition is not needed), and 0 for n = 2, 3 and 4, hence a(1) = 1/4 and a(n) = 0 for n = 2, 3 and 4.

The number of permutations of [n] with |p(i+1) - p(i)| >= 2, for i = 1..(n-1), for n >= n is given by A002464(n), for n >= 0. See also A001266(n) = A002464(n)/2, for n >= 2. These permutations are also called king permutations, e.g., in A382644.

Examples

			n = 5: the 4 permutations are 2 4 1 3 5, 3 1 4 2 5 and their reversals 5 3 1 4 2,  5 2 4 1 3.
a(5) = 1 = A382644(4)/2 = (A001236(5) - A242522(6))/2 = (7 - 5)/2, and A382644(5)/2 - A242522(6) = 6 - 5 = 1
a(6) = a(5) + A242522(6) = 1 + 5 = 6.
		

Crossrefs

Cf. A002464, A001266, A242522, A382644.

Formula

a(n) = A382644(n-1)/2, for n >= 5.

a(n) = (A001266(n) - A242522(n+1))/2, for n >= 5.

a(n) = A382644(n)/2 - A242522(n+1), for n >= 5.

a(n) = a(n-1) + A242522(n), for n >= 6, with a(5) = 1.