recurrence involving permutations

Solution 1:

(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.

You’ve already shown that

$$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<n-1$, 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.

Solution 2:

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.