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

George SPAHN and Doron ZEILBERGER

In fond memory of David Peter Robbins (12 August 1942 - 4 September 2003) who was a

great problem solver, and an equally good problem poser

Abstract: 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 Navarette, Robert Taurasu, David Robbins (to whose memory this article is dedicated), and John Riordan. We conclude with two proofs of John Riordan’s recurrence (from 1965) for the enumerating sequence for permutations that adjacent entries can’t have adjacent values (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.

Important: Maple Package and Output Files

This article is accompanied by a Maple package ResPerms.txt downloadable from

https://sites.math.rutgers.edu/~zeilberg/tokhniot/ResPerms.txt .

The front of this article

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/perms.html

contains many input and output files.

How it all Started

A few months ago we came across a lovely paper by Manuel Kauers and Christoph Koutschan [KK] where they described how to guess recurrences satisfied by ‘hard to compute sequences’ where one can get very plausible conjectured recurrences for sequences with far fewer ”data points” than is needed for traditional guessing with undetermined coefficients. As a very impressive case study they found a conjectured linear recurrence with polynomial coefficients enumerating the number of permutations π of {1, …, n} such that

π_{i+2} − π_{i} ≠ 2 .

This is sequence A189281 in the OEIS (https://oeis.org/A189281) [S22], that initially took a very long time to compute the first 35 terms, hence it was labeled hard, and there was no a priori theoretical guarantee that it is holonomic, i.e. satisfies a linear recurrence equation with polynomial coefficients, surprisingly turned out to most likely be one. The traditional vanilla method of of guessing a recurrence of order r and degree d requires at least (r + 1)(d + 1) + r + 1 data points, and the number of terms given in the OEIS at the time (computed, with lots of computer time and memory by Vaclav Kotesovec) did not work, one needed more data. Using their ingenious new method of ”guessing with little data” they conjectured a linear recurrence equation of order 8 and degree 11 (that would require (8 + 1) · (11 + 1) + 8 + 1 = 117 data points. They only used 35 terms! Assuming that conjecture is true one of us (DZ) found an equivalent recurrence of order 13 and degree 3 that would necessitate (13 + 1) · (3 + 1) + 13 + 1 = 70 data points (still twice as many).

But even with the new method one needs efficient ways to generate as many terms as possible. We would like to efficiently count the following two kinds of sequences, for any positive integers r and s

a_{r,s}(n) := #{π ∈ S_{n} | π_{i+r} − π_{r} ≠ s for all 1 ≤ i ≤ n − r} ,

and

b_{r,s}(n) := #{π ∈ S_{n} | |π_{i+r} − π_{r}| ≠ s for all 1 ≤ i ≤ n − r} .

(For any finite set S, #S denotes its number of elements).

Past Work

For the sequences a_{1,s} for any s, Enrique Navarrete found a beautiful explicit formula, using a clever inclusion-exclusion argument

Theorem (E. Navarrete [N]) for all s ≥ 1 and n ≥ s,

a_{1,s}(n) = ∑_{j=0}^{n−s}(−1)^{j}\binom{n − s}{j}(n − j)! .

Using the Zeilberger algorithm[Z1] we immediately get

Corollary For s ≥ 1 and for n ≥ 2 we have

a_{1,s}(n) = (n − 1) a_{1,s}(n − 1) + (n − s + 1) a_{1,s}(n − 2)

In the last section we will give a combinatorial proof.

The sequence b_{1,1}(n) is famous! It is sequence A2464 [S11a] https://oeis.org/A002464, called Hertzsprung’s problem, and its description in the OEIS is:

ways to arrange n non-attacking kings on an n × n board, with 1 in each row and column. Also number of permutations of length n without rising or falling successions.

The combinatorial giant, John Riordan [R] proved a nice fourth-order recurrence

b_{1,1}(n) = (n + 1) b_{1,1}(n − 1) − (n − 2) b_{1,1}(n − 2) − (n − 5) b_{1,1}(n − 3) + (n − 3) b_{1,1}(n − 4) .

We will later give two new proofs. The first using the continuous Almkvist-Zeilberger algorithm [AZ], and the second using an elegant combinatorial argument.

Our hero, Dave Robbins [R], used a clever inclusion-exclusion argument to prove the following double sum

b_{1,1}(n) = ∑_{i=0}^{n−1}(−1)^{i}(n − i)! ∑_{c=1}^{i} \binom{i − 1}{i − c}\binom{n − i}{c}2^{c} .

We will later use Dave Robbins’ approach to study, and efficiently compute, the sequences b_{1,s}(n) for s > 1, none of which are (yet) in the OEIS.

To conclude this historical section let’s mention which sequences are currently (Oct. 2022) in the OEIS:

• a_{1s}(n) for 1 ≤ s ≤ 5, see references [S11],[S12],[S13],[S14],[S15] respectively.

• a_{rr}(n) for 1 ≤ r ≤ 6, see references [S11],[S22],[S33],[S44],[S55],[S66] respectively.

• b_{rr}(n) for 1 ≤ r ≤ 6, see references [S11a],[S22a],[S33a],[S44a],[S55a],[S66a] respectively.

Mone of the sequences a_{rs}(n) and b_{rs}(n) with r > 1, s > 1 and r ≠ s are yet (Oct. 2022) in the OEIS.

In the next section we will show how to compute many terms of these new sequences and compute many more terms for the sequences a_{rr}(n) and b_{rr}(n), 2 ≤ r ≤ 6, that are already in the OEIS.

Semi-Efficient Computation of the sequences a_{r,s}(n)

We will use the old workhorse of inclusion-exclusion but with a new twist, that would make it amenable for symbolic computation.

Fix r ≥ 1 and s ≥ 1. We want to count all the good guys, i.e. permutations of {1, …, n} such that none of the following n − r unfortunate events are committed

π_{r+1} − π_{1} = s , π_{r+2} − π_{2} = s , …, π_{n} − π_{n−r} = s .

As usual, instead of counting good guys, we do a signed counting of all pairs,

[guy, S] ,

where guy is any permutation, and S is a subset (possibly empty, possibly the the whole) of its set of unfortunate events. (See [Z3] for an engaging account). Each such pair contributes (−1)#S to the total sum. While this new signed sum has many more terms, and is extremely inefficient when applied to specific sets, it isa great theoretical tool when used cleverly by humans (and computers!).

Looking at the structure of this possible set of unfortunate events, we see that the board {1, 2, …, n} has a certain subsest of the set of pairs

{{1, r + 1} , {2, r + 2} , …, {n − r, n}} ,

(right now we are ignoring entries of the permutation. Think of them as a collection of arcs r apart). Each such configuration naturally forms into a disjoint union of connected components. All the entries that do not participate are really singleton tiles. So looking at the possible connected components, we see a natural tiling of the ‘board’ {1, 2, …, n} into horizontal shifts of tiles of the form

{1} , {1, 1 + r} , {1, 1 + r, 1 + 2r} , {1, 1 + r, 1 + 2r, 1 + 3r} , ….

So let’s introduce variables x[1], x[2], x[3] … and declare that the weight of the tile t is x[#t]. In particular, the weight of a singleton is x[1]. The weight of a tiling is the product of the weights of all its constituent tiles.

Suppose that r = 2 and s = 3, n = 9 and the set of marked unfortunate events happens to be:

{π_{3} − π_{1} = 3 , π_{5} − π_{3} = 3 , π_{9} − π_{7} = 3} .

Since {1, 3} and {3, 5} form a connected component {1, 3, 5}, and {7, 9} forms its own connected component, and the integers not participating in these two connected components are all singletons, This gives the tiling

{{1, 3, 5} , {7, 9}, {2}, {4}, {6}, , {8}} .

So let’s define a polynomial in the (potentially infinite, but for any given n finite) set of variables x_{1}, x_{2}, x_{3}, …

f_{r,n}(x_{1}, x_{2}, x_{3} …) := ∑ T weight(T) ,

where the sum is taken over all the tilings of the board {1, 2, …, n} by the tiles (i.e. horizontal shifts) of

{1}, {1, 1 + r}, {1, 1 + r, 1 + 2r}, ….

For example

f_{3,5}(x_{1}, x_{2}, x_{3}) = x_{1}^{5} + 2x_{1}^{3}x_{2} + x_{1}x_{2}^{2} ,

since

• There is one tiling with all singletons (horizontal shifts of {1}:, namely

{{1}, {2}, {3}, {4}, {5}}

whose weight is x_{1}^{5}.

• There are two tilings with 3 singletons and one horizontal shifts of {1, 3}, namely

{{1, 4}, {2}, {3}, {5}} , {{2, 5}, {1}, {3}, {4}} ,

each of whose weight is x_{1}^{3}x_{2}.

• There is one tiling with 1 singleton and two horizontal shifts of {1, 3}, namely

{{1, 4}, {2, 5}, {3}} ,

whose weight is x_{1}x_{2}^{2}.

Using dynamical programming (see [Z2]) it is very fast to compute these polynomials. Since these weight-enumerators of tilings are so central to our approach, we invite our readers to convince themselves that

f_{3,7}(x_{1}, x_{2}, x_{3}) = x_{1}^{7} + 4x_{1}^{5}x_{2} + x_{1}^{4}x_{3} + 5x_{1}^{3}x_{2}^{2} + 2x_{1}^{2}x_{2}x_{3} + 2x_{1}x_{2}^{3} + x_{2}^{2}x_{3} .

This implemented in procedure fsn(r,n,x) in our Maple package.

But there is another tiling present. If you look at the values of the violations, you have a natural tilings with tiles

{1} , {1, 1 + s}, , {1, 1 + s, 1 + 2s} , {1, 1 + s, 1 + 2s, 1 + 3s} ,

whose weight-enumerator is f_{s,n}(x_{1}, x_{2}, …).

For example, look at the pair that comes up in trying to compute a_{2,3}(9)

[326195487, {π_{3} − π_{1} = 3, π_{5} − π_{3} = 3, π_{9} − π_{7} = 3}] ,

looking at the values we have the tiling

{{3, 6, 9}, {4, 7}, {1}, {2}, {5}, {6}} .

whose weight is also x_{1}^{4}x_{2}x_{3}.

Now write

f_{r,n}(x_{1}, …, x_{n}) = ∑ C_{α}^{(n,r)}x_{1}^{a_{1}}x_{2}^{a_{2}} ⋯ x_{n}^{a_{n}} ,

where the sum ranges over all integer partitions 1^{a_{1}}2^{a_{2}} … n^{a_{n}}, written in frequency notation, so 1 · a_{1} + 2 · a_{2} + … + n · a_{n} = n (note that if r = 1 all partitions show up, but when r > 1 then some never show up).

Finally we are ready to state our ‘formula’ for a_{r,s}(n).

a_{r,s}(n) = ∑ C_{α}^{(n,s)} · C_{α}^{(n,r)} · (−1)^{a_{1}+a_{2}+...+a_{n}−n}a_{1}!a_{2}! ⋯ a_{n}! ,

where the sum ranges over all partitions of n α = 1^{a_{1}}2^{a_{2}} … n^{a_{n}}, written in frequency notation.

Let’s explain. Any set of unfortunate events gives rise to two tilings one with tiles {1}, {1, 1 + r}.{1, 1 + r, 1 + 2r}, … care by the f_{r,n} and one with tiles {1}, {1, 1 + s}.{1, 1 + s, 1 + 2s}, …, taken care by the f_{s,n}. The cardinality of the set of resulting unfortunate events is

a_{1} · (1 − 1) + a_{2} · (2 − 1) + a_{3} · (3 − 1) + … = n − (a_{1} + … a_{n}) ,

explaining the exponent of −1. Finally, one has to match the ‘input tiles’ and the ‘output tiles’. Of course they have to be of the same size Any of the

• a_{1} singletons tiles in the input domain can go to any of the a_{1} singleton tiles of the output domain. More generally

• Any of the a_{i} tiles of size i of the input domain can go to any of the a_{i} tiles of the output domain. The total number of possible matches is thus:

a_{1}!a_{2}! ⋯ a_{n}! .

So we explained all the ingredients in our ‘formula’. A very small tweak gives the formula for b_{r,s}(n).

b_{r,s}(n) = ∑ C_{α}^{(n,s)} · C_{α}^{(n,r)} · (−1)^{a_{1}+a_{2}+...+a_{n}−n}a_{1}!a_{2}! ⋯ a_{n}! · 2^{a_{2}+a_{3}+...+a_{n}} ,

where the sum ranges over all partitions of n 1^{a_{1}}2^{a_{2}} … n^{a_{n}}, written in frequency notation. Since b_{r,s}(n) counts the number of permutations of {1, …, n} such that |π_{i+r} − π_{i}| ≠ s, now in each component of the tiling that is not a singleton can have two different direction, ‘totally up’ and ‘totally’ down. This accounts for the extra factor 2^{a_{2}+a_{3}+...+a_{n}} in our formula for b_{r,s}(n). Did we answer the enumeration question? Well, not quite! According to Herb Wilf’s classic essay [W] we need a polynomial time algorithm and the number of terms in our ‘formulas’ for a_{r,s}(n) and b_{r,s}(n) is the number of partitions of n (in fact slightly less, but not significantly less, asymptotically speaking). According to Hardy and Ramanujan they are about e^{π\sqrt{2n/3}} of them. Nevertheless our approach worked very well up to n = 60 and enabled us to get many more terms than they were previously in the OEIS, computed by FIDE International Problem Solving master Vaclav Kotesovec (btw these have a nice interpretation as ”non-attacking” fairy-chess pieces). For example to get the first 30 terms of the sequence a_{4,4}(n), that is https://oeis.org/A189283, it took less than three seconds on our modest laptop. Here there are: 1, 2, 6, 24, 114, 628, 4062, 30360, 255186, 2414292, 25350954, 292378968, 3673917102, 49928069188, 729534877758, 11403682481112, 189862332575658, 3354017704180052, 62654508729565554, 1233924707891272728, 25550498290562247438, 554913370184289495780, 12612648556263898345758, 299411750583810718488216,

7409924986737790240296258, 190856850583975937020030228, 5108283222440036893650974970, 141870112250977140975169694808, 4082973503947066134710463043374, 121616802487841972048586204012740 . For many terms of such sequences, including a_{r,s}(n) and b_{r,s}(n) with r > 1, s > 1 and r ≠ s, none of which are yet in the OEIS see the numerous output files in the front of this article:

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/perms.html .

The beautiful work of Roberto Taurasu We should mention that the case of b_{r,r}(n) for r = 2 and (larger r) has been nicely handled by Roberto Taurasu [T]. We believe that his approach bears some similarities to ours, but ours is more amenable to using symbolic computations efficiently. In particular the sequence b_{2,2}(n), currently has 35 terms listed in https://oeis.org/A110128 . See our output file

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oResPerms22Va.txt

for 60 terms! Polynomial-Time Algorithms for computing b_{1,s}(n) for all s As pointed out by Enrique Navarrete, the formula for a_{1,s}(n) is very simple, and as we pointed out already implies a very simple second-order recurrence. Dave Robbins [R] (and before him John Riordan) explored the sequence b_{1,1}(n) also using inclusion-exclusion but this time there are no more (potentially) infinitely-many tiles to keep track of, because the tiles in the ‘output’ domain are very simple, they are just sets of the form {1}, {1, 2}.{1, 2, 3}, dots, so one only needs to find the weight-enumerator of tiles according to the weight x^{T otalNumberOfT iles}, without recording the individuality of the tiles. But one has to keep track of the total length of the non-singleton tiles to one has to introduce another formal variable, let’s call it z that keeps track of that. Since each non-singleton tile can have two directions. The details can’t be gleanded from the Maple source code of procedures Ker1s(s, x, z, K). We believe that it can be proved that these Robbins-style weight-enumerators of tilings can be proved to be always rational functions, and being experimental mathematicians we just guessed them, so officially the output of the recurrences for these sequences for b_{1,s}(n) for s > 1 are only semi-rigorous. Thanks to Dave Robbins, our proof of Riordan’s recurrence is fully rigorous. Since at the end of the day once you have the Robbins-weight-enumerator K_{s}(x, z) for enumerating b_{1,s}(n), that is a rational function, one applies the umbra z^{n} → n!, but this is just like multiplying by e^{−z} and integrating from 0 to ∞.

Hence we have Semi-Rigorous Theorem For s ≥ 1, there almost exists a rational function of x and z (that Maple can find), let’s call it K_{s}(x, z) such that

∑_{n=0}^{∞} b_{1,s}(n)x^{n} = ∫_{0}^{∞} K_{s}(x, z)e^{−z} dz .

Using the Almkvist-Zeilberger algorithm [AZ] one can find an (inhomogeneous) differential equation with polynomial coefficients, that translates to a homogeneous linear recurrence with polynomial coefficients for the actual sequence b_{1,s}(n). See the output files

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oResPermsR1.txt
https://sites.math.rutgers.edu/~zeilberg/tokhniot/oResPermsR2.txt
https://sites.math.rutgers.edu/~zeilberg/tokhniot/oResPermsR3.txt
https://sites.math.rutgers.edu/~zeilberg/tokhniot/oResPermsR4.txt

for the sequence b_{1,1}(n), b_{1,2}(n), b_{1,3}(n), b_{1,4}(n), respectively. Combinatorial, Human-Generated, Proofs of the Linear Recurrences satisfied by a_{1,s}(n) and b_{1,1}(n). References

[AZ] Gert Almkvist and Doron Zeilberger, The Method of Differentiating Under The Integral Sign, J. Symbolic Computation 10 (1990), 571-591.

https://sites.math.rutgers.edu/~ zeilberg/mamarim/mamarimPDF/duis.pdf .

[KK] Manuel Kauers and Christoph Koutschan, Guessing with little Data,

https://arxiv.org/abs/2202.07966 .

[N] Enrique Navarrete, Generalized K-Shift Forbidden Substrings in Permutations,

https://arxiv.org/pdf/1610.06217.pdf

[Ri] John Riordan, A recurrence for permutations without rising or falling successions, Ann. Math. Statist. 36 (1965), 708-710.

[Ro] David P. Robbins, The probability that neighbors remain neighbors after random rearrangements, Amer. Math. Monthly 87 (1980), 122-124.

https://www.jstor.org/stable/2321990 .

[S11] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, sequence A255,

https://oeis.org/A000255.

[S11a] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, sequence A2464,

https://oeis.org/A002464.

[S12] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, sequence A55790,

https://oeis.org/A055790.

[S13] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, sequence A277609,

https://oeis.org/A277609.

[S14] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, sequence A277563,

https://oeis.org/A277563 .

[S15] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, sequence A280425,

https://oeis.org/A280425 .

[S22] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, sequence A189281,

https://oeis.org/A189281.

[S22a] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, sequence A110128,

https://oeis.org/A110128.

[S33] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, sequence A189282,

https://oeis.org/A189282.

[S33a] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, sequence A117574,

https://oeis.org/A117574.

[S44] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, sequence A189283,

https://oeis.org/A189283.

[S44a] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, sequence A189255, https://oeis.org/A189255

[S55] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, sequence A189284,

https://oeis.org/A189284.

[S55a] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, sequence A189256,

https://oeis.org/A189256.

[S66] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, sequence A189285,

https://oeis.org/A189285.

[S66a] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, sequence A189271,

https://oeis.org/A189271.

[SZ] George Spahn and Doron Zeilberger, Automatic Counting of Generalized Latin Rectangles and Trapezoids, Enumerative Combinatorics and Applications 2(1) (2022), Article S2R8.

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/ltrap.html .

[T] Roberto Taurasu, The Dinner Table Problem: The Rectangular Case, INTEGERS, 6 (2006), paper A11.

https://www.emis.de/journals/INTEGERS/papers/g11/g11.pdf .

[W] Herbert S. Wilf, What is an answer?, American Mathematical Monthly 89 (1982), 289-292.

[Z1] Doron Zeilberger, The method of cretive telescoping, J. Symbolic Computation 11(1991) 195-204.

http://sites.math.rutgers.edu/~zeilberg/mamarimY/CreativeTelescoping.pdf

[Z2] Doron Zeilberger, Automatic CounTilings, Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, Jan. 20, 2006.

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/tilings.html .

[Z3] Doron Zeilberger, Automatic Enumeration of Generalized Ménage Numbers, Séminaire Lotharingien de Combinatoire, 71 (2014), article B71a.

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/menages.html .

George Spahn and Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: gs828 at math dot rutgers dot edu , DoronZeil] at gmail dot com .

Written: Oct. 31, 2022.