Enumerative Combinatorics and Applications ecajournal.haifa.ac.il

ECA X:X (xxxx) Article #SxRx

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^{‡}

†Department of Mathematics, Rutgers University (New Brunswick) www.georgespahn.com

‡Department of Mathematics, Rutgers University (New Brunswick) Email: DoronZeil at gmail dot com

Received: April XX, xxxx, Accepted: August XX, xxxx, Published: August XX, xxxx The authors: Released under the CC BY-ND license (International 4.0)

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 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 state some open questions and pledge donations to the OEIS in honor of the solvers. We conclude with a postscript describing a clever bijection by Rintaro Matsuo, that we were made aware of after the first version was written, that suggests an alternative approach to our counting problem, and that implies that there always exists, for each specific r and s, a polynomial time algorithm for computing these sequences, and also gives strong evidence (but not yet proves) some of the open problems. But as r and s get larger, the implied degree of the “polynomial time algorithm” grows large enough to guarantee that our original, “exponential time” algorithms, are still useful.

Keywords: Permutations; Inclusion-Exclusion; Symbolic-Computation

2020 Mathematics Subject Classification: 05A05; 33F10

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

1. How It All Started

A few months ago we came across a lovely paper by Manuel Kauers and Christoph Koutschan [5] where they described how to guess recurrences satisfied by ‘hard to compute sequences’, where one gets very plausible conjectured recurrences for sequences with far fewer “data points” than are needed by traditional guessing with undetermined coefficients. As a very impressive case study they found a conjectured (but practically certain) linear recurrence with polynomial coefficients for the sequence enumerating permutations π of {1, …, n} such that for all 1 ≤ i ≤ n − 2, one has:

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

This is sequence A189281 in the OEIS (https://oeis.org/A189281) [11]. Initially the OEIS only had 35 terms, computed with great computing effort by Vaclav Kotesovec, hence it was labeled hard. There was no a priori theoretical guarantee that it is holonomic, i.e. satisfies a linear recurrence equation with polynomial coefficients, and for that matter, we still don’t have one, but surprisingly, even with this ‘little data’, Kauers and Koutschan, using their new method, were able to conjecture a linear recurrence equation of order 8 and degree 11. In general, using the traditional vanilla method of undetermined coefficients, in order to conjecture a recurrence of order r and degree d requires at least (r + 1)(d + 1) + r + 1 data points, hence to conjecture a recurrence of that order and degree would require (8 + 1) · (11 + 1) + 8 + 1 = 117 data points, rather than the at-the-time available 35 terms. Nevertheless, they succeeded using so little data!

George SPAHN and Doron ZEILBERGER

Assuming that the [5] conjecture was true, one of us (DZ) found an equivalent recurrence of order 13 and degree 3 that would only necessitate (13 + 1) · (3 + 1) + 13 + 1 = 70 data points (see [11, Seq. A189281]).

But even with the new method of [5], one needs efficient ways to generate as many terms as possible. Our goal is to compute many terms of the following two doubly-infinite families of sequences, for any given 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).

Using our method, we were able to compute from scratch, 70 terms of A189281, so in hindsight, one did not need the new Kauers-Koutschan method for this particular sequence, but we are sure that it would be useful in many other cases.

2. Past Work

For the sequences a_{1,s}(n), for any positive integer s, Enrique Navarrete found a beautiful and simple explicit formula, using a clever inclusion-exclusion argument [7].

Theorem 2.1 (E. Navarrete). 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 [14] we immediately get the following corollary.

Corollary 2.1. 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) .

Later we will give a combinatorial proof of this recurrence for a_{1,1}(n).

The sequence b_{1,1}(n) is famous! It is sequence A2464 [11] https://oeis.org/A002464, called Hertzsprung’s problem, and was already investigated by Paul Poulet [8] in 1919. Its description in the OEIS is as follows:

“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 [9], proved a nice fourth-order recurrence. For n ≥ 4

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 [4], and the second using an elegant combinatorial argument.

Our hero, Dave Robbins [10], used a clever inclusion-exclusion argument to prove the following double sum formula for b_{1,1}(n), n ≥ 2:

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 any s > 1, none of which are (yet) in the OEIS.

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

• a_{1s}(n) for 1 ≤ s ≤ 5, see references [11, Seq. A255, A55790, A277609, A277563, A280425] respectively.

• a_{rr}(n) for 1 ≤ r ≤ 6, see references [11, Seq. A255, A189281, A189282, A189283, A189284] respectively.

• b_{rr}(n) for 1 ≤ r ≤ 6, see references [11, Seq. A2464, A110128, A117574, A189255, A189256] respectively.

None 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. Neither are the sequences b_{1,s}(n) for s > 1, for which we will later give polynomial-time algorithms.

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

3. Computing as Many Terms as Possible of the sequences a_{r,s}(n) and b_{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 whole) of its set of unfortunate events. (See [16] 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 is a great theoretical tool when used cleverly by humans (and computers!).

Looking at the structure of such a 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}} ,

Think of them as a collection of arcs whose width is r . Each such configuration naturally forms into a disjoint union of connected components. All the entries that do not participate form 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 a 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. Let’s give a simple example.

Suppose that r = 2 and s = 3, n = 9 and the subset S, of the set of π’s 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, we have 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}, {1, 1 + r, 1 + 2r, 1 + 3r} , ….

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}):

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

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

• There are two tilings with 3 singletons and one horizontal shifts of {1, 4}, 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, 4}, namely

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

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

Using dynamical programming (see [15]), it is very fast to compute these polynomials. Since these weightenumerators 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 is implemented in procedure fsn(r,n,x) in our Maple package.

But there is another tiling present. If you look at the actual values of the ‘unfortunate events’, 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 one of the many pairs that come 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 (since π_{1} = 3, π_{3} = 6, π_{5} = 9 and π_{7} = 4, π_{9} = 7):

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

whose weight is the same as that of the corresponding input tiling, { {1, 3, 5} , {7, 9} , {2}, {4}, {5}, {8} }, namely 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}} of n, written in frequency notation. Note that, of course: 1 · a_{1} + 2 · a_{2} + ⋯ + n · a_{n} = n. (Also note that if r = 1 all integer partitions show up, but when r > 1 then some never do).

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}, … taken care by the f_{r,n} ; and

• one with tiles {1}, {1, 1 + s}.{1, 1 + r, 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), that comes from inclusion-exclusion. Finally, one has to match the ‘input tiles’ and the ‘output tiles’. Of course they have to be of compatible sizes.

• For each i, there are a_{i}! ways to match the a_{i} tiles of size i of the input tiling with the a_{i} tiles of the output tiling.

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.

The extra factor of 2^{a_{2}+a_{3}+···+a_{n}} in the summand comes from the fact that now we count permutations of {1, …, n} such that |π_{i+r} − π_{i}| ≠ s, hence now in each component of the tiling that is not a singleton, there are two possible directions, up and down.

The formulas for a_{r,s}(n) and b_{r,s}(n) are implemented by procedures Urs(r,s,n) and Vrs(r,s,n), respectively, in our Maple package ResPerms.txt .

4. Did we answer the enumeration question?

Well, not quite! According to Herb Wilf’s classic essay [13] 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, with relatively little computing effort, many more terms. These sequences were first computed by Vaclav Kotesovec, that according to his OEIS profile, is a FIDE International master in Chess Problems. (Kotesovec gives nice interpretations of these sequences in terms of “non-attacking” placements of some fairy-chess pieces).

Just to illustrate the (relative) efficiency of our new method, in order to get the first 30 terms of the sequence a_{4,4}(n) (https://oeis.org/A189283), we only needed 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.

Comment: After writing the first version, there were some interesting developments made by Rintaro Matsuo [6]. See the postscript.

5. The beautiful work of Roberto Tauraso

We should mention that the case of b_{r,r}(n) for r = 2 and (larger r) has been nicely handled by Roberto Tauraso [12]. 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 only 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!

Update: For 150 terms, see the Postscript.

6. 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 already mentioned, it implies (via the Zeilberger algorithm [14]), a very simple second-order recurrence. Dave Robbins [10] (and before him John Riordan [9] and even before him, Paul Poulet [8]) 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}, …, 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, so we need to introduce another formal variable, let’s call it z that keeps track of the total length of the non-singleton tiles. Also each non-singleton tile can have two directions so we would have to replace z by 2z. The details may be gleaned 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 are always rational functions, but being experimental mathematicians, we just guessed them, so officially the output of the recurrences for the sequences for b_{1,s}(n) with s > 1 are only semi-rigorous. (On the other hand, thanks to Dave Robbins, our automatic proof of Riordan’s recurrence for the case s = 1, i.e. for b_{1,1}(n), is fully rigorous.)

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 the same as multiplying by e^{−z}, and then integrating from 0 to ∞.

Hence we have the following theorem.

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) linear 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 ,

[This output file contains the first promised new proof of Riordan’s recurrence, using the Almkvist-Zeilberger algorithm].

   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.

7. Combinatorial, Human-Generated, Proofs of the Linear Recurrences satisfied by a_{1,1}(n) and b_{1,1}(n)

.

Proposition 7.1. Let a(n) = a_{1,1}(n). Then for n ≥ 2

a(n) = (n − 1) · a(n − 1) + (n − 2) · a(n − 2) .

Combinatorial Proof: We would like to count the number of permutations π that never have π_{i+1}−π_{i} = 1. Suppose we had such a permutation α, and we remove the n. We now have a permutation β of length n − 1. There are two cases. Either β has no i such that β_{i+1} −β_{i} = 1, or it has a violation, an i such that β_{i+1} −β_{i} = 1. Since α had no violations, the only possible violation in β is involving the 2 elements that used to be separated by n.

Case 1: There is no violation in β. There are a(n − 1) possibilities for β in this case. In each one, there are n possible locations we could insert n to get a permutation of length n. As long as we don’t insert the n immediately after the n − 1, we will get a permutation of length n with no violations. Thus for each possible β, there are n − 1 possible α that could map to it. Thus the number of permutations in this case is equal to (n − 1) · a(n − 1).

Case 2: Removing n from α caused a single violation in β. Let us define an auxiliary sequence, b(n), which counts the number of permutations π of length n with a single i such that π_{i+1} − π_{i} = 1. Each possible π in this case, can be made into a permutation of length n with no violations by inserting n in between the 2 elements involved in the violation. Thus b(n − 1) counts the number of possibilities for α in case 2.

We now have that

a(n) = (n − 1) · a(n − 1) + b(n − 1) .

We next argue that

b(n) = (n − 1) · a(n − 1) .

Consider the operation f_{i} for 1 ≤ i ≤ n that maps permutations π of length n to permutations of length n + 1. f_{i}(π) is computed in the following way. First insert an i + 1 in π immediately after the i. Then relabel all elements j > i as j + 1. For example, f_{2}(321) = 4231. If we apply one of these operations f_{i} to a permutation with no violations, we get a permutation with exactly one violation. Further, any permutation with exactly one violation can be obtained by applying an f_{i} to a permutation with no violations. Thus the set of permutations described by b(n) are in bijection with {f_{i}(π)}, where π a permutation described by a(n − 1). There are n − 1 possibilities for i and a(n − 1) possibilities for π, so we get that indeed b_{n} = (n − 1) · a(n − 1). Thus

b(n − 1) = (n − 2) · a(n − 2) ,

and we get

a(n) = (n − 1) · a(n − 1) + (n − 2) · a(n − 2) .

   In a talk (https://www.youtube.com/watch?v=ahuY7FHPiAc) delivered at the conference ICECA 2022
(September 6-7, 2022) (http://ecajournal.haifa.ac.il/Conf/ICECA2022.html), the second-named author

(DZ) pledged to donate $100 to the OEIS in honor of the first person to find a combinatorial proof of Proposition 2 below. This challenge was met by the first-named author (GS). The donation was made.

Proposition 7.2. Now let a(n) = b_{1,1}(n). Then for n ≥ 4

a(n) = (n + 1) · a(n − 1) − (n − 2) · a(n − 2) − (n − 5) · a(n − 3) + (n − 3) · a(n − 4)

Combinatorial Proof: In this case we say a up-violation in a permutation π is an integer i so that π_{i+1} − π_{i} = 1 and a down-violation is an integer i so that π_{i+1} − π_{i} = −1. We now define 2 auxiliary sequences, b(n) and c(n).

• A(n) is the set of permutations of length n with no violations (of either kind).

• a(n) = #A(n)

• B(n) is the set of permutations of length n with exactly one violation (of either kind).

• b(n) = #B(n)

• C(n) is the set of permutations of length n with exactly one violation (of either kind) at specifically i = n − 1.

• c(n) = #C(n)

Lemma 7.1. For n ≥ 2

a(n) = (n − 2) · a(n − 1) + b(n − 1) − c(n − 1) .

For the proof, we first state that if you start with a permutation of length n − 1 with no violations, then there are n−2 locations that we can insert n into such that we still do not have any violations. Doing so only requires that we avoid inserting n next to n − 1. We can generate (n − 2) · a(n − 1) unique permutations in this manner. This will generate some of the permutations in A(n) but not all. The others are permutations π such that if n is removed, we introduce a single violation. Removing n from π will give an element of B(n − 1), but not all elements of B(n − 1) can be reached. If we have an element of B(n − 1) that is also an element of C(n − 1), then inserting n will introduce a new violation, so we will not get a permutation in A(n). In summary, any permutation in B(n)\C(n) can be expanded into an element of A(n) by inserting n between the violation. This gives all remaining elements of A(n), so we get that a(n) = (n − 2) · a(n − 1) + b(n − 1) − c(n − 1)

Lemma 7.2. For n ≥ 2

b(n) = 2(n − 1) · a(n − 1) + 2b(n − 1) + b(n − 2)

We can obtain most of the elements of B(n) in the following way. Start with an element of A(n − 1), π. As in the proof of Proposition 1, we will use an operation similar f_{i} to expand one elements i into either i, i + 1 or i + 1, i, and increase the value of each element j ∈ π, j > i by 1. So the function outputs expanding i into an up-violation or a down-violation. For example, f_{1}(53142) = {641253, 642153}. Then there (n − 1) choices for i, a(n − 1) choices for π, and 2 choices for whether it expands into an up-violation or down-violation. This gives 2(n−1)·a(n−1) elements of B(n), and like last time it only remains to count the ones where the inverse of this procedure introduces new violations. For example 4213 and 4132 would collapse to 312 and not be generated by an element of A(n − 1). These elements collapse to a permutation with at least one violation. The ones that collapse to having exactly one violation end up in B(n − 1). Each permutation α in B(n − 1) can be expanded into a permutation in B(n) in 2 ways. Suppose α has an up-violation at i. Then we replace i with the downviolation i+1, i, and increase all j > i by 1. This necessarily fixes the previous violation, and does not introduce any violations. Alternatively, we could replace i+1 with i+2, i+1, which would have the same effect. If instead α had a down violation, i+1, i, you could replace it with i+2, i, i+1, or i+1, i+2, i. There are always exactly 2 permutations in B(n) which map down to each permutation in B(n − 1), so we get 2b(n − 1) contributions from this case. We also have to account for the possibility that after collapsing we have both new possible violations. For example 1324 would collapse to 123 which is not in B(n − 1). Luckily we can further collapse this triple violation and end up with a permutation in B(n − 2). Thus b(n) = 2(n − 1) · a(n − 1) + 2b(n − 1) + b(n − 2).

Lemma 7.3. For n ≥ 2

c(n) = 2a(n − 1) + c(n − 1) .

For this one, we can start with an element of A(n − 1) and insert the n next to the n − 1 to get an element of C(n). There are 2 places we can insert it, so we get 2·a(n−1) unique elements of C(n) in this way. We then have the elements of C(n) where removing n causes n−1 to be adjacent to n−2. The number of permutations in this case is exactly c(n−1). All elements of C(n) fall into one of the two cases, so we get c(n) = 2a(n−1)+c(n−1).

The above 3 lemmas give a system of 3 recurrences and 3 equations. We can solve this using (noncommutative) linear algebra. Letting N be the negative shift operator,

N f(n) := f(n − 1) ,

and using a, b, c to refer to the sequences as a whole, we get:

a = (n − 2)Na + Nb − Nc
b = 2(n − 1)Na + 2Nb + N^{2}b
c = 2Na + Nc

Solving for a using Gaussian elimination, and the fact that Nn = (n − 1)N, gives

[1 − (n + 1) + (n − 2)N^{2} + (n − 5)N^{3} − (n − 3)N^{4}]a = 0 ,

so we conclude that

a(n) = (n + 1) · a(n − 1) − (n − 2) · a(n − 2) − (n − 5) · a(n − 3) + (n − 3) · a(n − 4) .

8. Final Challenges

Challenge 1 ($100 to the OEIS in honor of the first prover or disprover) Rigorously prove the recurrence conjectured in [5] for the sequence a_{2,2}(n) (or the equivalent one found by DZ) given in [11, Seq. A189281].

Challenge 2 ($200 to the OEIS in honor of the first conjecturer) Using the method of [5] or otherwise, conjecture a recurrence for the sequence b_{2,2}(n), whose first 60 terms are given here:

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

(Of course you are welcome to generate more terms! Update: see the postscript for 150 terms).

Update: Rintaro Matsuo (see the postscript) used his method to generate 600 terms! This enabled Manuel Kauers and Christoph Koutschan to meet this challenge. A donation to the OEIS in honor of Matsuo, Kauers, and Koutschan has been made.

Challenge 2’ (Additional $100). Prove it rigorously.

Challenge 3 ($300 to the OEIS in honor of the first prover or disprover) Prove (or disprove) that for every r > 1 and s > 1, the sequences a_{r,s}(n) and b_{r,s}(n) are always holonomic (alias P-recursive), in other words are satisfied by some homogeneous linear recurrence equation with polynomial coefficients. [Currently (as far as we know) there is no ‘general theory’ that would imply this.]

9. Postscript: Rintaro Matsuo’s Brilliant Bijection

After the first version of this article was written, we were made aware (via the OEIS) that Rintaro Matsuo [6] found a polynomial time algorithm (O(n^{4}) for each single term, and hence O(n^{5}) for the first n terms), to compute the sequence a_{2,2}(n), that was the starting point of our paper. He also implemented it and produced

300 terms of https://oeis.org/A189281.

The key insight of Matsuo is the bijection of the set {1, …, n} to itself given by

(1, 2, 3, …, n) → (1 , 1 + ⌊\frac{n + 1}{2}⌋ , 2 , 2 + ⌊\frac{n + 1}{2}⌋ , 3 , 3 + ⌊\frac{n + 1}{2}⌋, …)

that transforms the set of permutations of length n such that π_{i+2} − π_{i} ≠ 2 to a superset of the much easier set of permutations such that π_{i+1} −π_{i} ≠ 1, except that one is allowing π_{i+1} −π_{i} = 1 if i = ⌊\frac{n+1}{2}⌋ or π_{i} = ⌊\frac{n+1}{2}⌋. The Maple package ResPermsRM.txt, available from

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

gives a Maple implementation of Rintaro Matsuo’s algorithm [procedure U22rm(n)]. For the first 150 terms see:

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

However, we can also use inclusion-exclusion (after applying Matsuo’s bijection). Procedure RIN(n,a,b) uses inclusion-exclusion to compute, more generally, in time O(n^{5}), the first n terms of the set of permutations π such that π_{i+1} − π_{i} ≠ 1 except possibly if i = a or p_{i} = b, for any 1 ≤ a, b ≤ n − 1.

It is very likely that the three-variable function RIN(n, a, b) is holonomic in all its variables (i.e. satisfies linear recurrences with coefficients that are polynomials of (n, a, b) in each of the three variables). A possible strategy would be to guess it from empirical data and then prove that it satisfies some recurrences linking RIN(n, a, b) to its neighbors, obtained from combinatorial considerations, and then take the ‘diagonal’ RIN(n, ⌊\frac{n+1}{2}⌋, ⌊\frac{n+1}{2}⌋), that would have to be holonomic in n.

Using Matsuo’s bijection we wrote the absolute value analog, that enabled us to generate 150 terms for the companion sequence b_{2,2}(n), https://oeis.org/A110128, see:

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

With some optimization, and a larger computer, this can probably be extended to at least 300 terms. Using an adaptation of his original approach, Rintaro Matsuo generated 600 terms, and this enabled Manuel Kauers to conjecture a linear recurrence of order 24 and degree 40 satisfied by this sequence, giving yet more evidence that the sequence a_{r,s}(n) and b_{r,s}(n) are always P -recursive.

[To see Kauers’ conjecture based on Matsuo’s data type Ope22KKv(n,N) in the Maple package ResPermsRM.txt] .

Matsuo’s bijection, and its natural extensions, suggest a whole new research direction. Given finite sets of positive integers A and B, efficiently compute, and study, the sequences, let’s call them R_{A,B}(n), of permutations of {1, …, n} that π_{i+1} − π_{i} ≠ 1 except that π_{i+1} − π_{i} = 1 is allowed if i ∈ A or π_{i} ∈ B. One can also make the elements of A and B depend on n.

Also of interest is the absolute value version, i.e. counting permutations of {1, …, n} such that |π_{i+1}−π_{i}| ≠ 1 except that |π_{i+1} − π_{i}| = 1 is allowed, whenever i ∈ A or π_{i} ∈ B, for n ≥ max(A ∪ B). One can use an extension of Matsuo’s approach, or our inclusion-exclusion version (or both). Either way should give a polynomial time algorithms. Alas, the implied degree in the ‘polynomial time’ would be eventually prohibitive. More importantly, this suggests, but by no means proves, that these sequences are indeed always P -recursive (holonomic), i.e. satisfy a linear recurrence equation with polynomial coefficients.

We will be very happy if you, dear readers, will pursue all these ramifications. In particular design and implement O(n^{6}) algorithms to compute a_{3,3}(n) and b_{3,3}(n).

10. Maple Packages and Output Files

This article is accompanied by two Maple packages, ResPerms.txt, and ResPermsRM.txt, downloadable, respectively, from

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

The front of this article

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

contains many input and output files.

References

[1] A. T. Benjamin and J. J. Quinn, Proofs that Really Count: The Art of Combinatorial Proof, Mathematical Association of America, Washington, DC (2003).

[2] A. Blecher, C. Brennan, and A. Knopfmacher, Levels in bargraphs, Ars Math. Contemp. 9 (2015), 287–300.

[3] R. P. Stanley, Enumerative Combinatorics, Volume I, Cambridge University Press, Cambridge, UK (1997).

[4] G. Almkvist and D. 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 .

[5] M. Kauers and C. Koutschan, Guessing with little Data, Proceedings of ISSAC’22, 83-90.

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

[6] R. Matsuo, O(n^{4}) code to calculate a(n),

    [It is linked from https://oeis.org/A189281 ] .

[7] E. Navarrete, Generalized K-shift forbidden substrings in permutations,

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

[8] P. Poulet, Query 4750: Permutations, L’Intermédiaire des Mathématiciens 26 (1919), 117-121. [See the OEIS entry https://oeis.org/A002464 for scans of its pages]

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

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

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

[11] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2023. Available at https://oeis.

    org.

[12] R. Tauraso, The dinner table problem: the rectangular Case, INTEGERS, 6 (2006), paper A11.

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

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

[14] D. Zeilberger, The method of creative telescoping, J. Symbolic Computation 11(1991) 195-204,

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

[15] D. 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 .

[16] D. 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 .