# recurrence involving permutations

Let $$K_n$$ be the number of permutations $$\pi$$ of $$\{1,2,\cdots, n\}$$ so that $$|i-j|=1$$ implies $$|\pi(i)-\pi(j)| \leq 2$$ for all $$i,j$$ in $$\{1,2,\cdots, n\}$$. Show that for $$n\ge 2, K_{n+5} - K_{n+4} - K_{n+3} + K_n = 4.$$

I know recurrence relations that can be used to derive the answer. However, I don't understand how those recurrences were obtained, so could someone elaborate or provide a proof on that? Below are the recurrences I'm confused about.

Let $$A_n$$ be the number of permutations $$\pi$$ of $$K_{n+1}$$ with $$\pi(1) = 1$$, where $$K_1 := 1$$. Then

$$K_n = 2(A_0+A_1+\cdots + A_{n-3}+A_{n-1})\,\forall n\ge 2$$

and

$$A_n = A_{n-1}+A_{n-3} + 1$$ for $$n\ge 3$$.

Also, one has the following recurrences:

Assume $$n\ge 3$$. Let $$U_n$$ be the number of permutations counted by $$K_n$$ that end with $$n-1,n$$, let $$V_n$$ be the number ending in $$n,n-1$$, let $$W_n$$ be the number starting with $$n-1$$ and ending in $$n-2,n$$, let $$T_n$$ be the number ending in $$n-2,n$$ but not starting with $$n-1$$, and let $$S_n$$ be the number that has $$n-1,n$$ consecutively in that order but not at the beginning or end of a permutation.

(Why is it true that) every permutation $$\pi$$ counted by $$K_n$$ either lies in exactly one of the sets counted by $$U_n, V_n, W_n, T_n, S_n$$ or is the reverse of such a permutation.

Thus $$P_n = 2(U_n + V_n + W_n+ T_n+S_n)$$.

Also one has the recurrence relations $$U_{n+1} = U_n + W_n + T_n, V_{n+1 } = U_n, W_{n+1} = W_n, T_{n+1} = V_n, S_{n+1} = S_n + V_n$$.

I get that $$W_n = 1$$ for all $$n$$; $$n-1$$ must be beside $$n-3$$, $$n-2$$ must follow $$n-4,$$ etc. So a permutation in $$W_n$$ would have to be of the form $$(n-1,n-3,n-5,\cdots, n-4, n-2,n)$$. If $$n$$ is odd, in the middle of the permutation is $$2,1$$ and if n is even there is $$1,2$$.

Clearly every permutation counted by $$U_n, W_n, V_n, S_n, T_n$$ lies in the set of permutations counted by $$K_n$$. Now suppose $$\pi$$ is a permutation counted by $$K_n$$ that does not lie in $$U_n, W_n, V_n, S_n,$$ or $$T_n$$ and is not the reverse of a permutation lying in $$U_n, W_n, V_n, S_n,$$ or $$T_n$$. $$n$$ must be paired with $$n-1$$ or $$n-2$$ in any permutation counted by $$K_n$$. We cannot have $$\pi(n) = n$$ or $$\pi(1) = n$$ (otherwise $$\pi$$ is counted by $$U_n, W_n$$ or $$T_n$$ or is the reverse of a permutation counted by $$U_n, W_n,T_n$$). So $$\pi(i)=n$$ for some $$2\leq i\leq n-1$$. By the above observation, either $$\pi(i-1) = n-1$$ or $$\pi(i-1) = n-2$$. If it's the former then $$\pi$$ is counted by $$S_n$$ or is the reverse of a permutation counted by $$V_n$$ and if it's the latter then it's either counted by $$V_n$$ or is the reverse of a permutation counted by $$S_n$$. This covers all possibilities, so we are done the proof of this claim.

So to summarize, this question asks to justify/prove the recurrences for $$K_n$$ (just the first one if the proof above is right; permutations in the sets of permutations counted by $$U_n, V_n, W_n, S_n, T_n$$ are in bijection with their reverses), the recurrence for $$A_n$$ and the recurrences for $$U_n, W_n, V_n, S_n, T_n$$.

As an example to clarify the sets $$U_n, V_n, W_n, T_n, S_n$$ for $$n=3$$, we have $$U_n = \{(1,2,3)\}, V_n=\{(1,3,2)\}, W_n=\{(2,1,3)\}, T_n=\emptyset, S_n=\emptyset$$.

• @TeresaLisbon I think you misread the question. It's totally possible for $\pi(1)$ to equal $n$ or $n-1$; in that case $\pi(2)$ would have to be either $n - 2$ or $n-1$ (if $\pi(1)=n$) and $n, n-2,n-3$ (if $\pi(1)=n-1$). There's no "symmetric permutation" that's equal to its reverse, and one can verify that the reverse of such a permutation is not included in any of the sets $U_n, V_n, W_n, T_n, S_n$. Dec 14, 2021 at 14:18
• Oh my word, I totally misread it! I'm so sorry, but that's good news because it means that I can focus upon the question itself. Having said that , I'd still love it if you had a source for the question : not that I need it but if it contains more such questions , then that is what I'm looking for. Dec 14, 2021 at 14:47

(Apart from answering pings I am no longer active at MSE, but I was specifically asked by the OP to look at this question and have found the time to do so.)

I will use $$K_n$$ for the set of permutations of $$[n]$$ defined in the question and $$k_n=|K_n|$$ for the number of such permutations. Similarly, I will use $$U_n$$ for the set of permutations of $$[n]$$ ending in $$n-1,n$$ and $$u_n=|U_n|$$ for the number of such permutations, and so on.

$$k_n=2(u_n+v_n+w_n+s_n+t_n)\,.\tag{1}$$

The arguments for the next five recurrences are similar.

Suppose that $$\pi\in U_{n+1}$$. Then $$\pi$$ ends in $$n,n+1$$, and there are three possibilities:

• $$\pi$$ ends in $$n-1,n,n+1$$; then $$\pi\upharpoonright[n]\in U_n$$.
• $$\pi$$ ends in $$n-2,n,n+1$$, and $$\pi(1)=n-1$$; then $$\pi\upharpoonright[n]\in W_n$$.
• $$\pi$$ ends in $$n-2,n,n+1$$, and $$\pi(1)\ne n-1$$; then $$\pi\upharpoonright[n]\in T_n$$.

Conversely, appending $$n+1$$ to any permutation in $$U_n\cup W_n\cup T_n$$ yields a permutation in $$U_{n+1}$$, so $$u_{n+1}=u_n+w_n+t_n\,.\tag{2}$$

Suppose that $$\pi\in V_{n+1}$$; then $$\pi$$ ends in $$n+1,n$$. The only numbers that may be adjacent to $$n+1$$ are $$n$$ and $$n-1$$, so $$\pi$$ must end in $$n-1,n+1,n$$. Define a permutation $$\pi'$$ of $$[n]$$ by setting $$\pi'(n)=n$$, $$\pi'(n-1)=n-1$$, and $$\pi'\upharpoonright[n-2]=\pi\upharpoonright[n-2]$$. (In other words, $$\pi'$$ is obtained from $$\pi$$ by deleting $$n+1$$.) The map $$\pi\mapsto\pi'$$ is a bijection from $$V_{n+1}$$ to $$U_n$$, so $$v_{n+1}=u_n\,.\tag{3}$$

Suppose that $$\pi\in W_{n+1}$$; then $$\pi$$ begins with $$n$$ and ends in $$n-1,n+1$$. The only numbers that may be adjacent to $$n$$ are $$n-2,n-1$$, and $$n+1$$, so in fact $$\pi$$ must begin with $$n,n-2$$, and $$\pi\upharpoonright[n]$$ is the reversal of a permutation in $$W_n$$. Conversely, if $$\pi\in W_n$$, then reversing $$\pi$$ and appending $$n+1$$ yields a permutation in $$W_{n+1}$$ so $$w_{n+1}=w_n\,.\tag{4}$$

Suppose that $$\pi\in T_{n+1}$$; then $$\pi$$ ends in $$n-1,n+1$$ and does not start with $$n$$. Since $$\pi$$ does not start with $$n$$, $$n$$ has two neighbors in $$\pi$$, and clearly neither is $$n+1$$, so $$n$$ must be between $$n-1$$ and $$n-2$$. Thus, $$\pi$$ must end in $$n-2,n,n-1,n+1$$, and $$\pi\upharpoonright[n]\in V_n$$. Now suppose that $$\pi\in V_n$$, so that $$\pi$$ ends in $$n,n-1$$. The other neighbor of $$n$$ must be $$n-2$$, so $$\pi$$ ends in $$n-2,n,n-1$$, and appending $$n+1$$ yields a member of $$T_{n+1}$$. Thus, $$t_{n+1}=v_n\,.\tag{5}$$

Suppose that $$\pi\in S_{n+1}$$; then there is an index $$\ell$$ such that $$2\le\ell\le n-1$$, $$\pi(\ell)=n$$, and $$\pi(\ell+1)=n+1$$. Then $$\pi(\ell+2)=n-1$$, since the only possible neighbors of $$n+1$$ are $$n$$ and $$n-1$$. There are two possibilities:

• If $$\ell=n-1$$, then $$\pi$$ ends in $$n,n+1,n-1$$. Define a permutation $$\pi'$$ of $$[n]$$ by setting $$\pi'(n)=n-1$$ and $$\pi'\upharpoonright[n-1]=\pi\upharpoonright[n-1]$$; then $$\pi'\in V_n$$.
• If $$\ell, then deleting $$n+1$$ and reversing the result produces a member of $$S_n$$.

Clearly this defines a bijection from $$S_{n+1}$$ to $$S_n\cup V_n$$, so $$s_{n+1}=s_n+v_n\,.\tag{6}$$

Clearly $$w_3=1$$, so $$(4)$$ implies that $$w_n=1$$ for all $$n\ge 3$$. From $$(3)$$ and $$(6)$$ we see that $$s_{n+1}=s_n+u_{n-1}\,,\tag{7}$$ and from $$(3)$$ and $$(5)$$ that $$t_{n+1}=u_{n-1}\,,\tag{8}$$ and hence from $$(2)$$ that $$u_{n+1}=u_n+u_{n-2}+1\,.\tag{9}$$

Note that the definition of $$U_n$$ actually makes sense for $$n=$$ and $$n=2$$, with $$u_1=0$$ and $$u_2=1$$, and it’s easy to check that $$(7),(8)$$, and $$(9)$$ then hold for all $$n\ge 3$$. In fact we can also set $$s_2=0$$, which is consistent with the definition of $$S_n$$, and see that $$(7)$$ holds for $$n\ge 2$$.

It follows from $$(9)$$ that $$u_{n+5}-u_{n+4}=u_{n+2}+1$$ and hence that

\begin{align*} u_{n+5}-u_{n+4}-u_{n+3}+u_n&=u_{n+2}-u_{n+3}+u_n+1\\ &=(u_{n+2}+u_n+1)-u_{n+3}\\ &=u_{n+3}-u_{n+3}\\ &=0 \end{align*}\tag{10}

for all $$n\ge 1$$. Then

\begin{align*} v_{n+5}-v_{n+4}-v_{n+3}+v_n&=u_{n+4}-u_{n+3}-u_{n+2}+u_{n-1}=0\,,\\ w_{n+5}-w_{n+4}-w_{n+3}+w_n&=1-1-1+1=0\,,\text{ and}\\ t_{n+5}-t_{n+4}-t_{n+3}+t_n=&u_{n+3}-u_{n+2}-u_{n+1}+u_{n-2}=0 \end{align*}\tag{11}

for all $$n\ge 3$$. Moreover,

\begin{align*} s_{n+5}-s_{n+4}-s_{n+3}+s_n&=(s_{n+4}+s_{n+3}+s_{n+2}+s_{n-1})+(u_{n+4}+u_{n+3}+u_{n+2}+u_{n-1})\\ &=s_{n+4}+s_{n+3}+s_{n+2}+s_{n-1} \end{align*}

for all $$n\ge 2$$.

Using $$(7)$$ and $$(9)$$ we can calculate directly that $$s_3=0$$, $$s_4=1$$, $$s_5=2$$, $$s_6=4$$, and $$s_7=8$$, so that

$$s_7-s_6-s_5+s_2=8-4-2+0=2\,,$$

and hence $$s_{n+5}-s_{n+4}-s_{n+3}+s_n=2\tag{12}$$ for all $$n\ge 2$$. $$(1),(10),(11)$$, and $$(12)$$ then imply that

$$k_{n+5}-k_{n+4}-k_{n+3}+k_n=2(s_{n+4}-s_{n+3}-s_{n+2}+s_{n-1})=4$$

for all $$n\ge 3$$. The simplest way to verify that $$k_{n+5}-k_{n+4}-k_{n+3}+k_n=4$$ also holds when $$n=2$$ is to use the recurrences already proved to calculate $$k_2$$ through $$k_7$$, as shown in the following table:

$$\begin{array}{c|cc} n&u_n&v_n&w_n&s_n&t_n&k_n\\\hline 1&0&&&&&1\\ 2&1&&&0&&2\\ 3&1&1&1&0&0&6\\ 4&2&1&1&1&1&12\\ 5&4&2&1&2&1&20\\ 6&6&4&1&4&2&34\\ 7&9&6&1&8&4&56 \end{array}$$

Thus, $$k_7-k_6-k_4+k_2=56-34-20+2=4$$, as desired.

This leaves only the two identities involving the sets $$A_n$$:

$$a_n=a_{n-1}+a_{n-3}+1\tag{13}$$

for $$n\ge 3$$, and

$$k_n=2\left(a_{n-1}+\sum_{i=0}^{n-3}a_i\right)\tag{14}$$

for $$n\ge 2$$.

To prove $$(13)$$, fix $$n\ge 3$$. Suppose that $$\pi\in A_n$$; then $$\pi(1)=1$$, and $$\pi(2)$$ must be either $$2$$ or $$3$$. If $$\pi(2)=2$$, define a permutation $$\pi'$$ of $$[n-1]$$ by setting $$\pi'(i)=\pi(i+1)-1$$ for each $$i\in[n]$$. Then it’s straightforward to check that $$\pi'\in A_{n-1}$$, and that the map $$\{\pi\in A_n:\pi(2)=2\}\to A_{n-1}:\pi\mapsto\pi'$$ is a bijection. This accounts for $$a_{n-1}$$ elements of $$A_n$$.

Now suppose that $$\pi(2)=3$$; there are two cases. If $$\pi(3)=2$$, so that $$\pi$$ begins with $$1,3,2$$, define a permutation $$\pi'$$ of $$[n-3]$$ by setting $$\pi'(i)=\pi(i+3)-3$$ for each $$i\in[n-3]$$. As in the previous case it’s straightforward to check that $$\pi'\in A_{n-3}$$, and that the map $$\{\pi\in A_n:\pi(2)=2\}\to A_{n-3}:\pi\mapsto\pi'$$ is a bijection. This accounts for another $$a_{n-3}$$ elements of $$A_n$$.

The only possible neighbors of $$2$$ are $$1,3$$, and $$4$$, so if $$\pi(3)\ne 2$$, then $$2$$ must have only the single neighbor $$4$$, and $$\pi$$ must end in $$4,2$$. In particular, $$\pi$$ must be $$1,3,4,2$$ if $$n=3$$ and $$1,3,5,4,2$$ if $$n=4$$. At this point it should be clear that if $$n=2m$$, then $$\pi$$ must be $$1,3,\ldots,2m-1,2m,\ldots,4,2$$, and if $$n=2m+1$$, then $$\pi$$ must be $$1,3,\ldots,2m+1,2m,\ldots,4,2$$. I’ll leave the proof by induction on $$n$$ to you; it’s a little tricky to write up but is not actually hard.

This proves $$(13)$$; that last case accounts for one last element of $$A_n$$, and the three cases are exhaustive and mutually exclusive. (Note that $$(13)$$ and $$(9)$$ are essentially the same recurrence; if you calculate a few values of $$a_n$$, you’ll find that $$a_n=u_{n+2}$$ for all $$n\ge 0$$.)

To prove $$(14)$$, for $$n\ge 2$$ let

$$b_n=a_{n-1}+\sum_{i=0}^{n-3}a_i\,.$$

Then

\begin{align*} b_{n+5}-b_{n+4}-b_{n+3}+b_n&=a_{n+4}-a_{n+3}-a_{n+2}+a_{n-1}\\ &\quad+\sum_{i=0}^{n+2}a_i-\sum_{i=0}^{n+1}a_i-\sum_{i=0}^na_i+\sum_{i=0}^{n-3}a_i\\ &=a_{n+4}-a_{n+3}-a_{n+2}+a_{n-1}\\ &\quad+\color{red}{\sum_{i=n-2}^{n+2}a_i-\sum_{i=n-2}^{n+1}a_i}-\color{blue}{\sum_{i=n-2}^na_i}\\ &=a_{n+4}-a_{n+3}-a_{n+2}+a_{n-1}+\color{red}{a_{n+2}}-\color{blue}{\sum_{i=n-2}^na_i}\\ &=a_{n+4}-a_{n+3}+a_{n-1}-a_n-a_{n-1}-a_{n-2}\\ &=(a_{n+4}-a_{n+3})-a_n-a_{n-2}\\ &=(a_{n+1}+1)-a_n-a_{n-2}\tag{by (13)}\\ &=(a_{n+1}-a_n)-a_{n-2}+1\\ &=(a_{n-2}+1)-a_{n-2}+1\\ &=2\,, \end{align*}

so if we set $$c_n=2b_n$$ for $$n\ge 2$$, we have $$c_{n+5}-c_{n+4}-c_{n+3}+c_n=4$$ for $$n\ge 2$$. Thus, the sequences $$\langle k_n:n\ge 2\rangle$$ and $$\langle c_n:n\ge 2\rangle$$ satisfy the same fifth order recurrence. It is now straightforward to verify by direct calculation that $$c_n=k_n$$ for $$n=2,\ldots,6$$ and hence that $$(14)$$ holds.

• Wonderful answer, thanks Prof. Scott! Wonder if you will be coming back any time soon to this site. This site is nothing wihtout your guidance. Dec 18, 2021 at 15:31
• @James: You’re very welcome. I’m afraid that I’m not likely to return any time soon: I left partly because of increased demands on my time elsewhere that have priority and partly because of increasing frustration with The Powers That Be and the way that certain things are handled here, and neither of those seems likely to change in the foreseeable future. But thank you for your kind words. Dec 18, 2021 at 22:08
• Though I am a beginner at MSE, I feel sorry that a great advisor like you has to leave. Take care wherever you are. Dec 20, 2021 at 0:35
• @Hermis14: Thank you, and the same to you. Dec 20, 2021 at 1:06

I'll use a slightly different notation from yours, by using uppercase letters (such as $$U_n,V_n$$ etc) for sets of permutations and the lowercase versions ($$u_n,v_n$$ etc) for the count of elements in those sets.

Given three integers parameters with $$a,n,b$$ with $$a$$ and $$b$$ not of the same parity and $$n\geq a, n\geq b$$, there is a unique finite sequence $$s$$ satisfying (i) $$s$$ starts with $$a$$ and ends with $$b$$, (ii) The maximum value of $$s$$ is $$n$$, (iii) $$s$$ starts by going up by $$+2$$ a certain number of times, then moving by $$\pm 1$$ once, and finally going down $$-2$$ a certain number of times. I call this sequence the upwards hat associated to $$a,n,b$$, and denote it by $$H(a,n,b)$$.

Symmetrically, one can define a downwards hat as follows : the condition $$n\geq a, n\geq b$$ is replaced by $$n\leq a,n\leq b$$, in (ii) we replace maximum with minimum, and in (iii) the slopes are $$-2,\pm 1,+2$$ instead of $$+2,\pm 1,-2$$. I also use $$H(a,n,b)$$ to denote downwards hats ; no confusion is possible because for a given $$(a,n,b)$$, we cannot have both an upwards and a downwards hat.

Given a finite sequence $$s$$, denote by $$P(s,n)$$ the set of all permutations in $$K_n$$ starting with $$s$$ (and $$p(s,n)$$ its count of elements).

Remark 1 (Intermediate value theorem for permutations in $$K_n$$) If $$\pi \in K_n$$, $$I_1$$ is a subinterval of $$[|1..n|]$$ and $$a \lt b$$ are two values in the image $$\pi(I_1)$$, then this image intersects any sequence of three consecutive integers in $$[a,b]$$.

This intermediate value property will be used mainly in the two following corollaries :

Remark 2 (Barrier property) Suppose that $$\pi \in K_n$$, and for some $$s,t$$ we have $$\pi([1 \ldots s]) \supseteq \lbrace t,t+1,t+2 \rbrace$$. Then $$\pi([s+1,n])$$ is all on one side of the "barrier" $$\lbrace t,t+1,t+2 \rbrace$$ ; either all the elements in $$\pi([s+1,n])$$ are $$\lt t$$ or they are all $$\gt t+2$$.

Remark 3 Suppose that $$\pi \in K_n$$, and for some $$s,t$$ we have $$\pi([1\ldots s]) \supseteq \lbrace t,t+1,t+2 \rbrace$$. Then $$\pi([1,s])$$ contains either $$1$$ or $$n$$.

Lemma 4 (Impossible prefixes). (a) If $$\pi\in K_n (n\geq 5)$$, then $$\pi$$ cannot start with $$134$$.

(b) If $$\pi\in K_n (n\geq 4)$$, then $$\pi$$ cannot start with $$23$$.

(c) If $$\pi\in K_n (n\geq 4)$$ and $$2 \lt x \lt n-1$$, then $$\pi$$ cannot start with $$x(x-1)$$ or $$x(x+1)$$.

Proof of lemma 4. (a) $$134$$ cannot only be followed by either a $$2$$ (which forces $$n=4$$) or $$1345$$, which creates the barrier $$345$$ preventing $$\pi$$ from ever reaching $$2$$. (b) $$23$$ can only be followed by a $$1$$ (otherwise $$1$$ will never be reached), which forces $$n=3$$. (c) We treat the case of $$x(x-1)$$ (the case of $$x(x+1)$$ is symmetrical). Suppose that $$\pi\in K_n$$ starts with $$x(x-1)$$. If $$\pi(3)\in\lbrace x+1,x-2 \rbrace$$, then $$\lbrace \pi(1),\pi(2),\pi(3)\rbrace$$ is a barrier, so by remark 3 it must contain $$1$$ or $$n$$ ; which is impossible by the hypotheses on $$x$$ on $$n$$. So necessarily $$\pi(3)=x-3$$. Let $$j$$ be the smallest index in $$[3..n]$$ such that $$\pi(j)\gt x$$ (it exists since $$x\lt n-1$$), Then $$\pi(j-1)\leq x$$ by construction, and since $$|\pi(j)-\pi(j-1)|\leq 2$$ we cannot help having $$x-1$$ or $$x$$ in $$\lbrace \pi(j-1),\pi(j)\rbrace$$, contradicting the injectivity of $$\pi$$. This finishes the proof of lemma 4.

Lemma 5 (Forced prefixes). (a) If $$\pi\in K_n (n\geq 5)$$ starts with $$135$$, then $$\pi=H(1,n,2)$$.

(b) If $$\pi\in K_n (n\geq 4)$$ starts with $$24$$, then $$\pi=H(2,n,1)$$.

(c) If $$\pi\in K_n (n\geq 5)$$ starts with $$x(x-2)$$ (for $$2\lt x\lt n-1$$), then it starts with $$H(x,1,x-1)$$.

(d) If $$\pi\in K_n (n\geq 5)$$ starts with $$x(x+2)$$ (for $$2\lt x\lt n-1$$), then it starts with $$H(x,n,x+1)$$.

Proof of lemma 5. (a) Let $$j$$ be the smallest index such that $$\pi(j)\neq 2j-1$$. Then $$j\geq 4$$, $$\pi$$ starts with $$135\ldots (2j-3)$$ and the next value $$\pi(j)$$ satisfies $$\pi(j)\neq 2j-1$$. So $$\pi(j+2)\in\lbrace 2j-4,2j-2 \rbrace$$. If $$\pi(j+2)=2j-4$$, then in $$\pi([1\ldots(j+2)])$$ we have the barrier $$\lbrace t_0,t_0+1,t_0+2\rbrace$$ (with $$t_0=2j-5$$), which forces $$2j-3=n$$ by Remark 3. The remaining values to be reached by $$\pi$$ are the even integers between $$2$$ and $$2j-4$$, and clearly there is only one admissible way to traverse them. We are therefore done in this case. So we are left with the case $$\pi(j+2)=2j-2$$. In this case, the even integers between $$2$$ and $$2j-4$$ must be reached before any other values if they are to be reached at all ; the last of them to be reached will be a $$2$$, so we are done also in this case.

(b) This is similar to (a), with the indices translated by $$1$$ (notice first that $$\pi$$ must start with $$246$$, otherwise it starts with $$243$$ which forces $$n=3$$, or $$245$$ which forces $$n=5$$).

(c) Let $$j$$ be the smallest index such that $$\pi(j)\neq x+2-2j$$. Then $$j\geq 3$$, $$\pi$$ starts with $$x(x-2)\ldots(x+4-2j)$$ and the next value $$\pi(j)$$ satisfies $$\pi(j)\neq x+2-2j$$. Then $$\pi(j)\in \lbrace x+3-2j,x+5-2j\rbrace$$.

If $$\pi(j)=x+5-2j$$, then in $$\pi([1\ldots(j)])$$ we have the barrier $$\lbrace t_0,t_0+1,t_0+2\rbrace$$ (with $$t_0=x+4-2j$$), which forces $$x+4-2j=1$$ by Remark 3. So $$x=2j-3$$ is odd, and $$\pi$$ starts with $$(2j-3)(2j-5) \ldots 12$$. The even integers from $$4$$ to $$2j-4$$ must be reached before any other values if they are to be reached at all, which forces $$\pi$$ to start with $$H(x,1,x-1)$$ as wished.

So we are left with the case $$\pi(j)=x+3-2j$$. In this case, the values $$x+5-2j,x+7-2j,\ldots,x-1$$ must be reached before any other values if they are to be reached at all, which forces $$\pi$$ to start with $$H(x,x+3-2j,x-1)$$. Then in $$\pi([1\ldots(2j-2)])$$ we have the barrier $$\lbrace t_0,t_0+1,t_0+2$$ (with $$t_0=x+3-2j$$), which forces $$x+4-2j=1$$ by Remark 3. This finishes the proof of (c).

(d) This is symmetrical to (c).

From Lemma 5 we deduce various bijections between sets of permutations, summarized by this list ($$n\geq 5$$ and $$x$$ denotes an integer satisfying $$2\lt x \lt n-1$$) :

$$\begin{array}{rl} P(12,n) \to P(1,n-1),& 12s_3\ldots s_n \mapsto 1(s_2-1)\ldots(s_n-1) \\ P(132,n) \to P(1,n-3),& 132s_4\ldots s_n \mapsto 1(s_4-3)\ldots(s_n-3) \\ P(21,n) \to P(1,n-2),& 21s_3\ldots s_n \mapsto (s_3-2)\ldots(s_n-2) \\ P(x(x-2),n) \to P(1,n-x),& H(x,1,x-1)s_{x+1}\ldots s_n \mapsto (s_{x+1}-x)\ldots(s_n-x) \\ P(x(x+2),n) \to P(x-1,x-1),& H(x,n,x+1)s_{n+2-x}\ldots s_n \mapsto s_{n+2-x}\ldots s_n \\ \end{array}\tag{6}$$

From those bijections we deduce equalities between certain counts (remember that $$n\geq 5, 2\lt x \lt n-1$$) :

$$\begin{array}{rcl} p(12,n) &=& p(1,n-1) \\ p(132,n) &=& p(1,n-3) \\ p(135,n) &=& 1 \\ p(21,n) &=& p(1,n-2), \\ p(24,n) &=& 1 \\ p(x(x-2),n) &=& p(1,n-x) \\ P(x(x+2),n) &=& p(x-1,x-1) \\ \end{array}\tag{7}$$

Next, let us introduce the symmetry $$i(t)=n+1-t$$. It is easy to see that $$\pi \in K_n$$ iff $$i\circ \pi\in K_n$$. It follows that for any finite sequence $$s=s_1s_2\ldots s_r$$,

$$p(s_1s_2\ldots s_r,n)=p(i(s_1)i(s_2)\ldots i(s_r),n) \tag{8}$$

In particular, $$p(n,n)=p(1,n)$$, so that (7) can be rewritten

$$\begin{array}{rcl} p(12,n) &=& p(1,n-1) \\ p(132,n) &=& p(1,n-3) \\ p(135,n) &=& 1 \\ p(21,n) &=& p(1,n-2), \\ p(24,n) &=& 1 \\ p(x(x-2),n) &=& p(1,n-x) \\ P(x(x+2),n) &=& p(1,x-1) \\ \end{array}\tag{7'}$$

Grouping some elements above, we deduce (remember that $$n\geq 5, 2\lt x \lt n-1$$) :

$$\begin{array}{rcl} p(1,n) &=& p(1,n-1)+p(1,n-3)+1 \\ p(2,n) &=& p(1,n-2)+1 \\ p(x,n) &=& p(1,n-x)+p(1,x-1) \\ \end{array}\tag{9}$$

The first line of (9) above is of course the inequality you denoted by $$a_n=a_{n-1}+a_{n-3}+1$$. Next, we have for $$n\geq 5$$

$$\begin{array}{lcl} k_n &=& \sum_{j=1}^n p(j,n) \\ &=& p(1,n)+p(2,n)+\sum_{j=2}^{n-2} p(j,n)+p(n-1,n)+p(n,n) \\ &=& 2(p(1,n)+p(2,n))+\sum_{x=3}^{n-2} p(x,n) \\ &=& 2(p(1,n)+p(1,n-2)+1)+\sum_{x=3}^{n-2} p(1,n-x)+p(1,x-1) \\ &=& 2(p(1,n)+p(1,n-2)+p(1,1))+2\sum_{j=2}^{n-3} p(1,j) \\ &=& 2(p(1,n)+\sum_{j=1}^{n-2} p(1,j)) \end{array}\tag{10}$$

It can be checked by hand that this last equality still holds for $$n=2,3,4$$ (although it fails for $$n=1$$).

Let us now look at the quantity $$d_n=k_{n+5}-k_{n+4}-k_{n+3}+k_n$$ for $$n\geq 2$$.

$$\begin{array}{lcl} \frac{d_n}{2} &=& b_{n+5}+\sum_{j=1}^{n+3} b_j-b_{n+4}-\sum_{j=1}^{n+2} b_j-b_{n+3}-\sum_{j=1}^{n+1} b_j+b_{n}+\sum_{j=1}^{n-2} b_j \\ &=& b_{n+5}-b_{n+4}-b_{n+3}+b_n +(b_{n+3}-b_{n+1}-b_n-b_{n-1}) \\ &=& b_{n+5}-b_{n+4} -b_{n+1}-b_{n-1} \\ &=& (b_{n+4}+b_{n+2}+1)-b_{n+4} -b_{n+1}-b_{n-1} \\ &=& b_{n+2}-b_{n+1}-b_{n-1}+1 \\ &=& 2 \\ \end{array}$$

This gives $$k_{n+5}-k_{n+4}-k_{n+3}+k_n=4$$, proving your claim.

• I was just about to finish an answer! Good job, +1, you've captured everything I found, and it was easy to go through the proof. I'll abort, I wonder if there are good generalizations. Dec 14, 2021 at 17:23
• Thanks for your kind remarks and upvote. The generalization with the condition $|\pi(i)-\pi(j)|\leq l$ with $l\gt 2$ probably gets messier as $l$ grows larger. Dec 14, 2021 at 17:30
• @EwanDelanoy thanks. I don't think the reverse of $\alpha,$ the permutation you gave to provide a counterexample to my claim is also in $T_n$. Could you also elaborate on some remarks (e.g. provide hints for proofs)? Dec 18, 2021 at 3:48
• @user3472 Thx for your feedback. I've removed from this answer all the stuff related to the set $U_n,V_n,W_n$ as they were not indispensable (and as they are treated in Brian M. Scott's answer). Dec 18, 2021 at 9:43
• @user3472 Regarding Remark 1, you can picture yourself a permutation in $K_n$ as a walker treading on a circular path made of $n$ successive stones. The hypothesis then says that the walker can jump over one or two stones, but not more. So to traverse a set of three successive stones the walker is forced to set foot on at least one of them. Dec 18, 2021 at 9:47