A110128 Number of permutations p of 1,2,...,n satisfying |p(i+2)-p(i)| not equal to 2 for all 0

1, 1, 2, 4, 16, 44, 200, 1288, 9512, 78652, 744360, 7867148, 91310696, 1154292796, 15784573160, 232050062524, 3648471927912, 61080818510972, 1084657970877416, 20361216987032284, 402839381030339816, 8377409956454452732

Offset: 0

Author

Roberto Tauraso, A. Nicolosi and G. Minenkov, Jul 13 2005

Keywords

• nonn
• nice

Comments

When n is even: 1) Number of ways that n persons seated at a rectangular table with n/2 seats along the two opposite sides can be rearranged in such a way that neighbors are no more neighbors after the rearrangement. 2) Number of ways to arrange n kings on an n X n board, with 1 in each row and column, which are non-attacking with respect to the main four quadrants.

a(n) is also number of ways to place n nonattacking pieces rook + alfil on an n X n chessboard (Alfil is a leaper [2,2]) [From Vaclav Kotesovec, Jun 16 2010]

Note that the conjectured recurrence was based on the 600-term b-file, not the other way round. - N. J. A. Sloane, Dec 07 2022

Links

• Rintaro Matsuo, Table of n, a(n) for n = 0..600 (terms up to a(35) from Vaclav Kotesovec)
• Manuel Kauers, Guessed recurrence operator of order 24 and degree 64
• Vaclav Kotesovec, Mathematica program for this sequence
• George Spahn and Doron Zeilberger, Counting Permutations Where The Difference Between Entries Located r Places Apart Can never be s (For any given positive integers r and s), arXiv:2211.02550 [math.CO], 2022.
• Roberto Tauraso, The Dinner Table Problem: The Rectangular Case, INTEGERS, vol. 6 (2006), paper A11. arXiv:math/0507293.

Crossrefs

Cf. A089222, A002464, A117574, A189281.

Column k=2 of A333706.

Formula

A formula is given in the Tauraso reference.

Asymptotic (R. Tauraso 2006, quadratic term V. Kotesovec 2011): a(n)/n! ~ (1 + 4/n + 8/n^2)/e^2.

a(n) ~ exp(-2) * n! * (1 + 4/n + 8/n^2 + 68/(3*n^3) + 242/(3*n^4) + 1692/(5*n^5) + 72802/(45*n^6) + 2725708/(315*n^7) + 16083826/(315*n^8) + 186091480/(567*n^9) + 32213578294/(14175*n^10) + ...), based on the recurrence by Manuel Kauers. - Vaclav Kotesovec, Dec 05 2022

Extensions

Edited by N. J. A. Sloane at the suggestion of Vladeta Jovovic, Jan 01 2008

Terms a(33)-a(35) from Vaclav Kotesovec, Apr 20 2012