Counting Permutations Where The Difference Between Entries Located r Places Apart Can never be s (For any given positive integers r and s)

By George Spahn and Doron Zeilberger

.pdf    .tex

In fond memory of David Peter Robbins (12 August 1942 - 4 September 2003) who was a great problem solver (see here), and an equally good problem poser

Given positive integers r and s, we use inclusion-exclusion, weighted-counting of tilings, and dynamical programming, in order to enumerate, semi-efficiently, the classes of permutations mentioned in the title. In the process we revisit beautiful previous work of Enrique Navarrete, Roberto Tauraso, David Robbins (to whose memory this article is dedicated), and John Riordan. We also present two new proofs of John Riordan’s recurrence (from 1965) for the sequence enumerating permutations without rising and falling successions (the r = 1, s = 1 case of the title in the sense of absolute value). The first is fully automatic using the (continuous) Almkvist-Zeilberger algorithm, while the second is purely human-generated via an elegant combinatorial argument. We then raise some open questions and pledge donations to the OEIS in honor of the solvers. We conclude with a postscript describing recent ideas of Rintaro Matsuo.

First Written: Nov. 3, 2022; This version (both paper and this web-page): Dec. 6, 2022.
Previous updates of this webpage, and Maple package (but not of the paper): Nov. 16, 2022 [implementing Rintaro Matsuo's O(n4) algorithm for a2,2(n)]

# Maple packages

• ResPerms.txt, a Maple package to efficiently count
permutations such that pi[i+r]-pi[i] ≠ s for any positive integers r and s, as well as
permutations such that |pi[i+r]-pi[i]| ≠ s, for any positive integers r and s,

• ResPermsRM.txt, Contains everything in ResPerms.txt, but with additional functions exploring Rintaro Matsuo's insights.

Added Nov. 10, 2022: The computer whiz Rintaro Matsuo found a much faster way to compute many terms of OEIS A189281, what we call a2,2(n) in our paper. He computed 300 terms! (in ten hours). See Rintaro Matsuo's C code. It would be nice if he can find more terms for other ar,s(n) and br,s(n).

Added Dec. 5, 2022: Rintaro Matsuo adapted his method to compute 600 terms of OEIS sequence A1110128, what we call b2,2(n) in our paper. We implmeented his method, and the "inclusion-exclusion" version, using his bijection in the current version of the Maple package ResPermsRM.txt. See output below.

# Sample Input and Output for ResPerms.txt

## Part I: conditions of the form πi+r - πi ≠ s

• If you want to see the first 69 terms, starting with n=1, of the number of permutations of length n such that πi+2i≠ 2 namely OEIS sequence A189281, then

the input gives the output.

Note that this gives yet-more-evidence to the Kauers-Koutschan conjectured recurrence (and its equivalent one of order 13 and degree 3), since now there are enough terms for traditional guessing, without their ingenious new approach that requires less data.

Added Nov. 16, 2022: As noted in OEIS sequence A189281, Rintaro Matsuo discovered a faster (polynomial time!) algorithm for this sequence. We implemented his method in Maple, and we got 100 terms in about 1400 seconds:
the input gives the output.

To get 150 terms take a bit longer (67018 seconds):
the input gives the output.

Added Nov. 25, 2022: Using Rintaro Matsuo's bijection, combined with Inclusion-Exclusion, to get the first 100 terms the input gives the output.

Added Dec. 5, 2022: Using the conjectured recurrence we get, semi-rigorously, many more terms. To get 2000 terms the input gives the output.

• If you want to see the first 64 terms, starting at n=1, of the number of permutations of length n such that πi+3i≠ 3, namely OEIS sequence A189282, then

the input gives the output.

• If you want to see the first 40 terms, starting at n=1, of the number of permutations of length n such that πi+4i≠ 4, namely OEIS sequence A189283, then

the input gives the output.

• If you want to see the first 40 terms, starting at n=1, of the number of permutations of length n such that πi+5i≠ 5, namely OEIS sequence A189284, then

the input gives the output.

• If you want to see the first 40 terms, starting at n=1, of the number of permutations of length n such that πi+6i≠ 6, namely OEIS sequence A189285, then

the input gives the output.

• If you want to see the first 40 terms, starting at n=1, of the number of permutations of length n such that πi+7i≠ 7, [not in the OEIS, viewed Aug. 12, 2022]

the input gives the output.

• If you want to see the first 40 terms, starting at n=1, of the number of permutations of length n such that πi+8i≠ 8, [not in the OEIS, viewed Aug. 12, 2022]

the input gives the output.

• If you want to see the first 48 terms, starting at n=1, of the number of permutations of length n such that πi+2i≠ 3, or, equivalently, πi+3i≠ 2, [not in the OEIS, viewed Aug. 12, 2022]

the input gives the output.

• If you want to see the first 40 terms, starting at n=1, of the number of permutations of length n such that πi+2i≠ 4, or, equivalently, πi+4i≠ 2, [not in the OEIS, viewed Aug. 12, 2022]

the input gives the output.

• If you want to see the first 40 terms, starting at n=1, of the number of permutations of length n such that πi+2i≠ 5, or, equivalently, πi+5i≠ 2, [not in the OEIS, viewed Aug. 12, 2022]

the input gives the output.

• If you want to see the first 40 terms, starting at n=1, of the number of permutations of length n such that πi+3i≠ 4, or, equivalently, πi+4i≠ 3, [not in the OEIS, viewed Aug. 12, 2022]

the input gives the output.

• If you want to see the first 40 terms, starting at n=1, of the number of permutations of length n such that πi+3i≠ 5, or, equivalently, πi+5i≠ 3, [not in the OEIS, viewed Aug. 12, 2022]

the input gives the output.

• If you want to see the first 100 terms of the number of permutations of length n such that pi[i+1]-pi[i] ≠ s for s from 1 to 10
the input gives the output.

## Part II: conditions of the form |πi+r - πi| ≠ s

• If you want to see the first 25 terms, starting with n=1, of the number of permutations of length n such that |πi+1i|≠ 1 and a recurrence satisfied by it (first proved by human John Riordan, see here, namely OEIS sequence A002464

then the input gives the output.

• If you want to see the first 60 terms, starting with n=1, of the number of permutations of length n such that |πi+2i|≠ 2 namely OEIS sequence A1110128

then the input gives the output.

Added Nov. 29, 2022: Using Rintaro Matsuo's map combined with Inclusion-Exclusion, we can get 100 terms.
the input gives the output.

Update Dec. 5, 2022: Rintaro Matsuo's used his method to generate 600 terms. Using this data, Manuel Kauers conjectured a recurrence of order 24 and degree 40 that can be gotten by typing
Ope22KKv(n,N)
in the Maple package ResPermsRM.txt,

Added Dec.6, 2022: Using Rintaro Matsuo's method (NOT using Inclusion-Exclusion) we can get 100 terms.
the input gives the output.

Added Dec.6, 2022: Using the CONJECTURED recurrence (found by Manuel Kauers based on Rintaro Matsuo's data) we can get 2000 terms of this sequence
the input gives the output.

• If you want to see the first 50 terms, starting with n=1, of the number of permutations of length n such that |πi+3i|≠ 3 namely OEIS sequence A117574, then

the input gives the output.

• If you want to see the first 50 terms, starting with n=1, of the number of permutations of length n such that |πi+4i|≠ 4 namely OEIS sequence A189255 then

the input gives the output.

• If you want to see the first 50 terms, starting with n=1, of the number of permutations of length n such that |πi+5i|≠ 5 namely OEIS sequence A189256 then

the input gives the output.

• If you want to see the first 50 terms, starting with n=1, of the number of permutations of length n such that |πi+1i|≠ 2 [not yet in the OEIS]

the input gives the output.

• If you want to see the first 40 terms, starting with n=1, of the number of permutations of length n such that |πi+1i|≠ 3 [not yet in the OEIS]

the input gives the output.

• If you want to see the first 40 terms, starting with n=1, of the number of permutations of length n such that |πi+1i|≠ 4 [not yet in the OEIS]

the input gives the output.

• If you want to see an article about the sequence enumerating permutations of length n such that |πi+1i|≠ 1

the input gives the output.

• If you want to see an article about the sequence enumerating permutations of length n such that |πi+1i|≠ 2

the input gives the output.

• If you want to see an article about the sequence enumerating permutations of length n such that |πi+1i|≠ 3

the input gives the output.

• If you want to see an article about the sequence enumerating permutations of length n such that |πi+1i|≠ 4

the input gives the output.