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


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

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.


    Doron Zeilberger's Home Page