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

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

Proposition 1: Let a(n) = a_{1,1}(n). Then

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

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) delived 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 2: Now let a(n) = b_{1,1}(n). Then

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

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 1:

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 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 down-violation 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 3:

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 (non-commutative) 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

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

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.