
%perms.tex: a Plain TeX file George Spahn and Doron Zeilberger
%Counting permutations such that Pi[i+r]-Pi[i]<>s
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\S{{\cal S}}
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\W{{\cal W}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\centerline
{\bf 
Counting Permutations Where The Difference Between Entries Located r Places Apart 
}
\centerline
{\bf
Can never be s (For any given positive integers r and s)
}
\bigskip
\centerline
{\it George SPAHN and Doron ZEILBERGER}

\bigskip




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

{\bf Proposition 1}: Let $a(n) = a_{1,1}(n)$. Then $$ a(n) = (n-1) \cdot a(n-1)+(n-2) \cdot a(n-2) \quad .$$

{\bf Proof}: We would like to count the number of permutations $\pi$ that never have $\pi_{i+1}-\pi_i=1$. Suppose we had such a permutation $\alpha$, and we remove the $n$. We now have a permutation $\beta$ of length $n-1$. There are two cases. Either $\beta$ has no $i$ such that $\beta_{i+1}-\beta_i=1$, or it has a violation, an $i$ such that $\beta_{i+1}-\beta_i=1$. Since $\alpha$ had no violations, the only possible violation in $\beta$ is involving the 2 elements that used to be separated by $n$.

{\bf Case 1}: There is no violation in $\beta$. There are $a(n-1)$ possibilities for $\beta$ 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 $\beta$, there are $n-1$ possible $\alpha$ that could map to it. Thus the number of permutations in this case is equal to $(n-1) \cdot a(n-1)$.

{\bf Case 2}: Removing $n$ from $\alpha$ caused a single violation in $\beta$. Let us define an auxiliary sequence, $b(n)$, which counts the number of permutations $\pi$ of length $n$ with a single $i$ such that $\pi_{i+1}-\pi_i=1$. Each possible $\pi$ 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 $\alpha$ in case 2. 

We now have that $$ a(n) = (n-1) \cdot a(n-1)+b(n-1) \, .$$
We next argue that $$b(n) = (n-1) \cdot a(n-1) \, .$$ 
Consider the operation $f_i$ for $1 \leq i \leq n$ that maps permutations $\pi$ of length $n$ to permutations of length $n+1$. $f_i(\pi)$ is computed in the following way. First insert an $i+1$ in $\pi$ 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(\pi)\}$, where $\pi$ a permutation described by $a(n-1)$. There are $n-1$ possibilities for $i$ and $a(n-1)$ possibilities for $\pi$, so we get that indeed $b_n = (n-1) \cdot a(n-1)$. Thus $$b(n-1) = (n-2) \cdot a(n-2) \, ,$$ and we get $$ a(n) = (n-1) \cdot a(n-1)+(n-2) \cdot a(n-2)\, . \quad \halmos$$ 

In a  talk ({\tt https://www.youtube.com/watch?v=ahuY7FHPiAc}) delived at
the conference  ICECA 2022 (September 6-7, 2022) ({\tt 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 {\bf combinatorial} proof of Proposition 2 below. This challenge was met by the first-named author (GS). The donation was made.

{\bf Proposition 2}: Now let $a(n) = b_{1,1}(n)$. Then $$ a(n) = (n+1) \cdot a(n-1)-(n-2) \cdot a(n-2)-(n-5) \cdot a(n-3)+(n-3) \cdot a(n-4) $$

{\bf Proof}: In this case we say a up-violation in a permutation $\pi$ is an integer $i$ so that $\pi_{i+1}-\pi_i=1$ and a down-violation is an integer $i$ so that $\pi_{i+1}-\pi_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)$

{\bf Lemma 1}: $$ a(n) = (n-2) \cdot 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) \cdot 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 $\pi$ such that if $n$ is removed, we introduce a single violation. Removing $n$ from $\pi$ 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) \setminus  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) \cdot a(n-1) +b(n-1) -c(n-1) $

{\bf Lemma 2}: $$ b(n) = 2(n-1) \cdot 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)$, $\pi$. 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 \in \pi$, $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 $\pi$, and 2 choices for whether it expands into an up-violation or down-violation. This gives $2(n-1) \cdot 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 $\alpha$ in $B(n-1)$ can be expanded into a permutation in $B(n)$ in $2$ ways. Suppose $\alpha$ 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 $\alpha$ 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) \cdot a(n-1) +2b(n-1) +b(n-2) $.

{\bf Lemma 3}: $$ c(n) = 2 a(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 \cdot 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) = 2 a(n-1) +c(n-1) $. 

The above 3 lemmas give a system of 3 recurrences and 3 equations. We can solve this using ({\bf non-commutative}) linear algebra. Letting $N$ be the {\bf negative} shift operator, 
$$
N\, f(n) := f(n-1) \quad,
$$
and using $a,b,c$ to refer to the sequences as a whole, we get:

$$ a = (n-2) N a + N b - N c $$
$$ b = 2(n-1) N a + 2 N b + N^2 b $$
$$ c = 2 N a + N c$$

Solving for $a$ using Gaussian elimination (and the fact that  $N n=(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) \cdot a(n-1)-(n-2) \cdot a(n-2)-(n-5) \cdot a(n-3)+(n-3) \cdot a(n-4) \, . \quad \halmos $$ 

\bigskip
\hrule
\bigskip
George Spahn and Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. \hfill\break
Email: {\tt  gs828 at math dot rutgers dot edu} \quad, \quad {\tt DoronZeil] at gmail dot com}   \quad .


Written: {\bf Oct. 31, 2022}.

\end