OFFSET
0,3
COMMENTS
In the notation of Spahn and Zeilberger (2022), this is b_{1,2}(n): permutations of 1..n in which no two adjacent entries differ by 2 (the case r=1, s=2 of avoiding |p(i+r)-p(i)| = s).
a(n)/n! -> exp(-2) as n -> infinity, the same limiting density as Hertzsprung's problem A002464 (where no two adjacent entries differ by 1).
LINKS
George Spahn and Doron Zeilberger, Counting Permutations Where The Difference Between Entries Located r Places Apart Can never be s, Enumerative Combin. Appl. 3:2 (2023), Article #S2R10. (arXiv:2211.02550 [math.CO] (2022), Zeilberger page linking other sequences)
FORMULA
G.f.: Sum_{n>=0} a(n)*z^n = Integral_{x=0..oo} exp(-x)*(x*z^3 - x*z^2 - z - 1)/((x*z^2 - x*z + z + 1)*(x*z^2 - 1)) dx (Spahn-Zeilberger, via the continuous Almkvist-Zeilberger algorithm; semi-rigorous).
D-finite (holonomic): a(n) satisfies an order-13 linear recurrence with polynomial coefficients (Spahn-Zeilberger, derived from the g.f. above via the Almkvist-Zeilberger algorithm): 2*(n+1)*(n+3)*a(n) - (3*n^2+23*n+32)*a(n+1) - (16*n^2+109*n+193)*a(n+2) + (18*n^2+114*n+114)*a(n+3) + (22*n^2+274*n+736)*a(n+4) - (20*n^2+264*n+684)*a(n+5) - (18*n^2+332*n+1364)*a(n+6) + (14*n^2+286*n+1288)*a(n+7) + (8*n^2+202*n+1136)*a(n+8) - (n+17)*(9*n+88)*a(n+9) + (2*n^2+41*n+213)*a(n+10) + (16*n+214)*a(n+11) - (4*n+70)*a(n+12) + 4*a(n+13) = 0.
EXAMPLE
For n=4 the permutations of {1,2,3,4} with no two adjacent entries differing by 2: of the 24 permutations, 8 survive: 1234, 1432, 2143, 2341, 3214, 3412, 4123, 4321.
PROG
(Python)
from math import factorial
from collections import defaultdict
def a(n):
# Inclusion-exclusion: edges {v, v+2} form two parity paths (odds, evens).
# Forcing j forbidden pairs adjacent (in runs) merges n values into n-j
# blocks; weight (-1)^j * 2^(#runs), times (n-j)! arrangements.
def poly(e): # coeff[j] = sum over j-edge subsets of (-1)^j * 2^(#runs)
dp = {(0, False): 1}
for _ in range(e):
nd = defaultdict(int)
for (j, prev), w in dp.items():
nd[(j, False)] += w
nd[(j+1, True)] += w * (-1 if prev else -2)
dp = nd
c = defaultdict(int)
for (j, _), w in dp.items(): c[j] += w
return [c[j] for j in range(e+1)]
po, pe = poly(max((n+1)//2-1, 0)), poly(max(n//2-1, 0))
conv = [0]*(len(po)+len(pe)-1)
for i, x in enumerate(po):
for k, y in enumerate(pe): conv[i+k] += x*y
return sum(c*factorial(n-j) for j, c in enumerate(conv))
print([a(n) for n in range(24)])
CROSSREFS
KEYWORD
nonn,easy,new
AUTHOR
James Shakarji, Jun 15 2026
STATUS
approved