Holonomicity of fixed-offset restricted-permutation counts

For fixed r,s≥1, let aᵣ,ₛ(n) count permutations forbidding πᵢ₊ᵣ−πᵢ=s and bᵣ,ₛ(n) count those forbidding the corresponding absolute difference. Are both sequences holonomic, meaning they satisfy polynomial-coefficient linear recurrences?

Why it matters and what counts as progress

Why it matters: An all-parameter result would extend isolated computed recurrences to an entire restricted-permutation family.

What counts as progress: A recurrence-existence proof for every fixed r,s, or a nonholonomic parameter pair; guessed finite-data recurrences require proof.

How the problem developed

2023 · Open challenge [1]
George Spahn and Doron Zeilberger Posed a challenge asking whether the restricted-permutation counts aᵣ,ₛ(n) and bᵣ,ₛ(n) are holonomic for every r,s>1.
11 Aug 2026 · Solution [2]
Jaideep Sai Padhi Reported an affirmative proof for both count families for all r,s>1, as one of five solved enumerative-combinatorics challenges.

AI contribution

Solutions to Five Challenge Problems in Enumerative and Algorithmic Combinatorics, with an Account of the Human-Machine Methodology Employed

Jaideep Sai Padhi

For every fixed r,s≥1, both restricted-permutation count sequences a_(r,s)(n), forbidding π_(i+r)−π_i=s, and b_(r,s)(n), forbidding the corresponding absolute difference, are claimed to be holonomic. The argument uses an interleaving bijection with finitely many seams and D-finite closure.

AI involvementAI-led

ImportanceNotable

Technical verificationPartial

Human understandingFew