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
Published in Enumeratice Combinatorics and Applications 3:2 (2023) Article S2R10.-
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)]
Added Aug. 14. 2026: entering Purdue freshman, Jaideep Sai Padhi (with the kind help of Claude) met Challenge 3 of the paper. Here is what he wrote:
I believe I have an answer. For every fixed r,s, both a_{r,s}(n) and b_{r,s}(n) are holonomic.
The argument is elementary, and much simpler than the prize suggests. Matsuo's bijection, which you and Spahn use only for (r,s) = (2,2), generalises directly. Relabel positions by interleaving the r arithmetic progressions of step r, and values by interleaving the s progressions of step s. Within a block, position-distance r becomes 1 and value-difference s becomes 1, so the condition becomes the ordinary adjacency condition, excused only where the interleaving breaks. Counting the breaks is a one-line argument: exactly r-1 on the position side and s-1 on the value side, giving an excusal set of size (r-1)+(s-1) for a_{r,s}, and (r-1)+2(s-1) for b_{r,s}, since in the absolute-value case both signs need excusing.
What matters is that these are bounded independently of n. That makes the two-layer inclusion-exclusion representation carry finitely many catalytic variables for each fixed (r,s), and holonomicity follows from the usual closure theorems: diagonals of rational functions, the Gamma-integral, sections and interlacing. No new machinery and no computation.
Everything is verified against brute force: the bijection for seven (r,s) pairs at 4 <= n <= 8, the seam counts, and the inclusion-exclusion representation itself in nine configurations. Note and scripts:
See here
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+2-πi≠ 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+3-πi≠ 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+4-πi≠ 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+5-πi≠ 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+6-πi≠ 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+7-πi≠ 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+8-πi≠ 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+2-πi≠ 3,
or, equivalently, πi+3-πi≠ 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+2-πi≠ 4,
or, equivalently, πi+4-πi≠ 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+2-πi≠ 5,
or, equivalently, πi+5-πi≠ 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+3-πi≠ 4,
or, equivalently, πi+4-πi≠ 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+3-πi≠ 5,
or, equivalently, πi+5-πi≠ 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+1-πi|≠ 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+2-πi|≠ 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+3-πi|≠ 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+4-πi|≠ 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+5-πi|≠ 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+1-πi|≠ 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+1-πi|≠ 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+1-πi|≠ 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+1-πi|≠ 1
the input gives the output.
If you want to see an article about the sequence enumerating permutations of length n such that |πi+1-πi|≠ 2
the input gives the output.
If you want to see an article about the sequence enumerating permutations of length n such that |πi+1-πi|≠ 3
the input gives the output.
If you want to see an article about the sequence enumerating permutations of length n such that |πi+1-πi|≠ 4
the input gives the output.
Doron Zeilberger's Home Page