A395335 - OEIS

%I #22 Jun 24 2026 23:59:33

%S 1,1,2,2,8,28,152,952,7208,62296,605864,6522952,76951496,986411272,

%T 13647501224,202653304456,3214170659528,54223248489064,

%U 969422707369448,18308139748071496,364185707232235784,7610646121718276392,166694564791285014056,3818542633160305746952

%N Number of permutations p of 1..n such that |p(i+1) - p(i)| <> 2 for all 1 <= i < n.

%C 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).

%C 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).

%H George Spahn and Doron Zeilberger, <a href="https://doi.org/10.54550/ECA2023V3S2R10">Counting Permutations Where The Difference Between Entries Located r Places Apart Can never be s</a>, Enumerative Combin. Appl. 3:2 (2023), Article #S2R10. (<a href="https://arxiv.org/abs/2211.02550">arXiv:2211.02550</a> [math.CO] (2022), <a href="https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/perms.html">Zeilberger page</a> linking other sequences)

%F 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).

%F 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.

%e 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.

%o (Python)

%o from math import factorial

%o from collections import defaultdict

%o def a(n):

%o     # Inclusion-exclusion: edges {v, v+2} form two parity paths (odds, evens).

%o     # Forcing j forbidden pairs adjacent (in runs) merges n values into n-j

%o     # blocks; weight (-1)^j * 2^(#runs), times (n-j)! arrangements.

%o     def poly(e):  # coeff[j] = sum over j-edge subsets of (-1)^j * 2^(#runs)

%o         dp = {(0, False): 1}

%o         for _ in range(e):

%o             nd = defaultdict(int)

%o             for (j, prev), w in dp.items():

%o                 nd[(j, False)] += w

%o                 nd[(j+1, True)] += w * (-1 if prev else -2)

%o             dp = nd

%o         c = defaultdict(int)

%o         for (j, _), w in dp.items(): c[j] += w

%o         return [c[j] for j in range(e+1)]

%o     po, pe = poly(max((n+1)//2-1, 0)), poly(max(n//2-1, 0))

%o     conv = [0]*(len(po)+len(pe)-1)

%o     for i, x in enumerate(po):

%o         for k, y in enumerate(pe): conv[i+k] += x*y

%o     return sum(c*factorial(n-j) for j, c in enumerate(conv))

%o print([a(n) for n in range(24)])

%Y Cf. A002464 (Hertzsprung's problem, the s=1 analog), A110128 (the r=s=2 sequence).

%K nonn,easy,changed

%O 0,3

%A _James Shakarji_, Jun 15 2026