Showing that $Q_n=D_n+D_{n-1}$

Let $$T_n$$ be the set of permutations of $$\{1,2,\ldots,n\}$$ which do not have $$i$$ immediately followed by $$i+1$$ for $$1\le i\le n-1$$; in other words, let \begin{align} T_n=\{\sigma \in S_n: \sigma(i)+1\ne\sigma(i+1) \text{ for all } 1\le i\le n-1\} . \end{align} Let $$Q_n$$ be the number of elements of $$T_n$$.

Let $$D_n$$ be the number of derangements of $$\{1,2,\ldots,n\}$$.

It is not hard to show algebraically that $$Q_n=D_n+D_{n-1}$$, but I am having difficulty coming up with a combinatorial argument to show why this is true. (I believe there are $$D_{n-1}$$ elements of $$T_n$$ that leave $$n$$ fixed, and $$D_n$$ elements of $$T_n$$ that move $$n$$, but I don't know how to justify this combinatorially.)

• just to be clear, "i followed by i+1" means that $\sigma(i)+1$ is never equal to $sigma(i+1)$, for all $i\leq n-1$ ? – Denis Jul 25 '13 at 0:52
• I'm sorry if my statement of the problem wasn't completely clear, but that's what I meant. (In other words, when you arrange the images of 1,..., n in order, i is never followed by i+1.) – user84413 Jul 26 '13 at 2:10
• It seems that your question has been asked and answered previously. I do have some doubt about Brian Scott's answer, and I've left a comment there requesting clarification, but it may just be a simple misunderstanding on my part. – Will Orrick Sep 10 '13 at 2:42
• @ Will Orrick Thank you for pointing out that my question had been asked previously. I read the answer posted, but I wasn't able to see how to make it work. (For example, it seemed to me that the permutations 1324 and 4132 would both map to the permutation 2314, if I am interpreting the answer correctly.) I like your argument to show that the number of elements of $T_n$ that fix n is equal to $D_{n-1}$, even though it isn't what I originally had in mind. Can you use the same idea to show that the number of elements in $T_n$ which do not fix n is equal to $D_n$? Thanks again. – user84413 Sep 10 '13 at 17:45
• It turns out Persi Diaconis, Steven Evans, and Ron Graham have a recent paper exploring this problem in some depth. (arxiv.org/abs/1308.5459 ) – Kevin P. Costello Oct 14 '13 at 23:53

(Note: this answer does not contain a bijection between the two sets, which is what the OP was originally hoping for, but it does show that the two counting problems are structurally equivalent and therefore have the same answer.)

The belief stated in the last paragraph of your question is correct: we can show that the set $\mathcal{D}_{n-1}$ of derangements of $\{1,2,3,\ldots,n-1\}$ and the set of permutations $\sigma$ of $\{1,2,3,\ldots,n\}$ with the properties

• $\sigma(n)=n$,
• $\sigma(i+1)\ne\sigma(i)+1,$ for $1\le i\le n-1,$

are equinumerous. That is, $\mathcal{D}_{n-1}$ and the set of elements of $T_n$ that fix $n$ have the same size. Call the latter set $\overline{T}_n.$

This result will prove the equation in your title since there is an obvious bijection between the set of elements of $T_n$ that do not fix $n$ and the set $\overline{T}_{n+1}$ of elements of $T_{n+1}$ that do fix $n+1,$ which will then be equinumerous with $\mathcal{D}_n.$

To enumerate $\mathcal{D}_{n-1}$, let $F=S_{n-1}$ be the set of permutations of $1,2,\ldots,n-1.$ Let $F_j$ be the set of elements of $F$ that fix $j,$ that is, elements $\sigma$ such that $\sigma(j)=j.$ In general, let $F_{ijk\ldots}=F_i\cap F_j\cap F_k\cap\ldots$ be the set of elements that fix $i,$ $j,$ $k,\ldots$, that is, elements $\sigma$ such that $\sigma(i)=i,$ $\sigma(j)=j,$ $\sigma(k)=k,\ldots$ Observe that $\lvert F_{i_1i_2\ldots i_k}\rvert=(n-1-k)!$ since only $n-1-k$ elements are free to move. Since the derangements are those elements that fix no element, the principle of inclusion-exclusion gives \begin{aligned}\lvert\mathcal{D}_{n-1}\rvert&=\lvert F\rvert-\sum_{i=1}^{n-1}\lvert F_i\rvert+\sum_{1\le i<j\le n-1}\lvert F_{ij}\rvert-\ldots\\ &=(n-1)!-\binom{n-1}{1}(n-2)!+\binom{n-1}{2}(n-3)!-\ldots\end{aligned}

To enumerate $\overline{T}_n$, let $G$ be the set of permutations of $1,2,\ldots,n$ that fix $n.$ Let $G_i,$ $1\le i\le n-1,$ be the subset of $G$ consisting of elements $\sigma$ such that $\sigma(i+1)=\sigma(i)+1.$ In general, let $G_{ijk\ldots}=G_i\cap G_j\cap G_k\cap\ldots$ be the set of elements of $G$ such that $\sigma(i+1)=\sigma(i)+1,$ $\sigma(j+1)=\sigma(j)+1,$ $\sigma(k+1)=\sigma(k)+1,\ldots$ We claim that, once again, $\lvert G_{i_1i_2\ldots i_k}\rvert=(n-1-k)!.$ This follows by noting that every constraint $\sigma(i_j+1)=\sigma(i_j)+1$ reduces the number of elements that can move independently by $1,$ leaving only $n-1-k$ elements that are free to move. One can imagine element $i$ becoming "glued" to element $i+1,$ so that they must move as a block.

For example, let $n=9$ and consider $G_{12478}.$ Since $8$ must immediately precede $9,$ which is fixed, and $7$ must immediately precede $8,$ which is now fixed as well, the elements $789$ are fixed. At the same time, $2$ must immediately precede $3$ and $1$ must immediately precede $2,$ meaning that the string $123$ can only move as a block. Similarly, the string $45$ can only move as a block. As a consequence the number of permutations in $G_{12478}$ is the number of ways of permuting the "objects" $123,$ $45,$ and $6,$ with the object $789$ fixed in place. So $G_{12478}=3!=(9-1-5)!,$ in agreement with the claim.

Since $\lvert G_{ijk\ldots}\rvert=\lvert F_{ijk\ldots}\rvert$ for all choices of subscripts, the principle of inclusion-exclusion implies that the computation of $\lvert\overline{T}_n\rvert$ is identical to that of $\lvert\mathcal{D}_{n-1}\rvert,$ so that they have the same final value: \begin{aligned}\lvert\overline{T}_n\rvert&=\lvert G\rvert-\sum_{i=1}^{n-1}\lvert G_i\rvert+\sum_{1\le i<j\le n-1}\lvert G_{ij}\rvert-\ldots\\ &=(n-1)!-\binom{n-1}{1}(n-2)!+\binom{n-1}{2}(n-3)!-\ldots\end{aligned}

Let $[a,b]=\{i\in\mathbf{Z}\mid a\le i\le b\}$ and let $[b]=[1,b].$ Let $S_{a,b}$ be the set of permutations of $[a,b]$ and let $S_n$ be the set of permutations of $[n].$ Let $\overline{S}_{a,b}=\{\sigma\in S_{a,b}\mid \sigma(b)=b\}$ be the set of permutations of $[a,b]$ that fix $b.$ Similarly, Let $\overline{S}_n=\{\sigma\in S_n\mid \sigma(n)=n\}$ be the set of permutations of $[n]$ that fix $n.$

The result will follow by exhibiting a bijective mapping $\rho_n:S_n\to\overline{S}_{n+1}$ that has the property that if $\sigma$ is an element of $S_n,$ $\tau$ is the element of $\overline{S}_{n+1}$ given by $\tau=\rho_n(\sigma),$ $f$ is an element of $[n],$ and $e$ is given by $\tau(e)=f,$ then the property $\tau(e+1)=\tau(e)+1=f+1$ holds if and only if $f$ is a fixed point of $\sigma.$

To define $\rho_n$ we introduce some notation. For distinct elements $i_1,\ldots,i_n\in[n]$ let $\langle i_1i_2\ldots i_n\rangle$ denote the element $\sigma\in S_n$ that satisfies $\sigma(j)=i_j$ for $1\le j\le n.$

We use usual cycle notation to represent swaps, which act from the left. So $(35)\langle123456\rangle=\langle125436\rangle,$ and $(23)(35)\langle123456\rangle=\langle135426\rangle.$ Every element of $S_n$ has a unique swap representation $(a_1b_1)(a_2b_2)\ldots(a_kb_k)\langle12\ldots n\rangle$ where $0\le k\le n-1,$ $a_1<a_2<\ldots<a_k,$ and $a_i<b_i$ for all $1\le i\le k.$ For example, $$\langle 326451\rangle=(13)\langle 126453\rangle=(13)(36)\langle 123456\rangle.$$ Observe that $f$ is a fixed point of $\sigma\in S_n$ if and only if $f$ does not appear among the $i_1,\ldots,i_k,j_1,\ldots,j_k$ in the swap representation of $\sigma.$

We define the insertion operator $[ai]:\overline{S}_{a+1,n+1}\to\overline{S}_{a,n+1},$ where $a\in[1,n]$ and $i\in[a,n].$ Let $\tau\in\overline{S}_{a+1,n+1}.$ Then $[ai]\tau$ is defined to be the element of $\overline{S}_{a,n+1}$ obtained by inserting $a$ immediately in front of $i+1.$ So, for example, $[24]\langle3546\rangle=\langle32546\rangle.$ Every element of $\overline{S}_{n+1}$ has a unique insertion representation $[1b_1][2b_2]\ldots[nb_n]\langle (n+1)\rangle,$ where $b_j\ge j$ for all $1\le j\le n.$ For example, \begin{aligned} &\langle 1456237\rangle=[13]\langle 456237\rangle=[13][22]\langle 45637\rangle =[13][22][36]\langle 4567\rangle\\ &=[13][22][36][44]\langle 567\rangle=[13][22][36][44][55]\langle 67\rangle=[13][22][36][44][55][66]\langle 7\rangle. \end{aligned} Observe that $a$ immediately precedes $a+1$ in $\tau\in\overline{S}_{n+1}$ if and only if the only occurrence of $a$ in the insertion representation of $\tau$ is of the form $[aa].$

The bijective mapping $\rho_n:S_n\to\overline{S}_{n+1}$ is now defined as follows. Let $\sigma\in S_n$ and compute the swap representation of $\sigma.$ We may add null swaps of the form $(aa)$ so that the swap representation of $\sigma$ takes the form $(1b_1)(2b_2)\ldots(nb_n)\langle 123\ldots n\rangle,$ where $b_j\ge j$ for all $1\le j\le n.$ Then define $\rho_n(\sigma)$ by replacing swaps with insertions and replacing $\langle 123\ldots n\rangle$ with $\langle (n+1)\rangle:$ $$\rho_n(\sigma)=[1b_1][2b_2]\ldots[nb_n]\langle (n+1)\rangle.$$

Examples: We show $\rho_3:S_3\to\overline{S}_4$ and $\rho_4:S_4\to\overline{S}_5$ explicitly. On the left, dots mark fixed points; on the right, overscores mark sequences of consecutive elements. \begin{aligned} \langle\dot{1}\dot{2}\dot{3}\rangle=(11)(22)(33)\langle123\rangle&\mapsto[11][22][33]\langle4\rangle=\langle\overline{1234}\rangle\\ \langle\dot{1}32\rangle=(11)(23)(33)\langle123\rangle&\mapsto[11][23][33]\langle4\rangle=\langle3\overline{12}4\rangle\\ \langle21\dot{3}\rangle=(12)(22)(33)\langle123\rangle&\mapsto[12][22][33]\langle4\rangle=\langle21\overline{34}\rangle\\ \langle231\rangle=(12)(23)(33)\langle123\rangle&\mapsto[12][23][33]\langle4\rangle=\langle1324\rangle\\ \langle312\rangle=(13)(23)(33)\langle123\rangle&\mapsto[13][23][33]\langle4\rangle=\langle3214\rangle\\ \langle3\dot{2}1\rangle=(13)(22)(33)\langle123\rangle&\mapsto[13][22][33]\langle4\rangle=\langle\overline{23}14\rangle \end{aligned} Observe that the two derangements, $\langle231\rangle$ and $\langle312\rangle,$ have images that contain no sequences of consecutive elements.

\begin{aligned} \langle\dot{1}\dot{2}\dot{3}\dot{4}\rangle=(11)(22)(33)(44)\langle1234\rangle&\mapsto[11][22][33][44]\langle5\rangle=\langle\overline{12345}\rangle\\ \langle\dot{1}\dot{2}43\rangle=(11)(22)(34)(44)\langle1234\rangle&\mapsto[11][22][34][44]\langle5\rangle=\langle4\overline{123}5\rangle\\ \langle\dot{1}32\dot{4}\rangle=(11)(23)(33)(44)\langle1234\rangle&\mapsto[11][23][33][44]\langle5\rangle=\langle3\overline{12}\,\overline{45}\rangle\\ \langle\dot{1}342\rangle=(11)(23)(34)(44)\langle1234\rangle&\mapsto[11][23][34][44]\langle5\rangle=\langle\overline{12}435\rangle\\ \langle\dot{1}423\rangle=(11)(24)(34)(44)\langle1234\rangle&\mapsto[11][24][34][44]\langle5\rangle=\langle43\overline{12}5\rangle\\ \langle\dot{1}4\dot{3}2\rangle=(11)(24)(33)(44)\langle1234\rangle&\mapsto[11][24][33][44]\langle5\rangle=\langle\overline{34}\,\overline{12}5\rangle\\ \langle21\dot{3}\dot{4}\rangle=(12)(22)(33)(44)\langle1234\rangle&\mapsto[12][22][33][44]\langle5\rangle=\langle21\overline{345}\rangle\\ \langle2143\rangle=(12)(22)(34)(44)\langle1234\rangle&\mapsto[12][22][34][44]\langle5\rangle=\langle42135\rangle\\ \langle231\dot{4}\rangle=(12)(23)(33)(44)\langle1234\rangle&\mapsto[12][23][33][44]\langle5\rangle=\langle132\overline{45}\rangle\\ \langle2341\rangle=(12)(23)(34)(44)\langle1234\rangle&\mapsto[12][23][34][44]\langle5\rangle=\langle24135\rangle\\ \langle2413\rangle=(12)(24)(34)(44)\langle1234\rangle&\mapsto[12][24][34][44]\langle5\rangle=\langle41325\rangle\\ \langle24\dot{3}1\rangle=(12)(24)(33)(44)\langle1234\rangle&\mapsto[12][24][33][44]\langle5\rangle=\langle1\overline{34}24\rangle\\ \langle312\dot{4}\rangle=(13)(23)(33)(44)\langle1234\rangle&\mapsto[13][23][33][44]\langle5\rangle=\langle321\overline{45}\rangle\\ \langle3142\rangle=(13)(23)(34)(44)\langle1234\rangle&\mapsto[13][23][34][44]\langle5\rangle=\langle21435\rangle\\ \langle3\dot{2}1\dot{4}\rangle=(13)(22)(33)(44)\langle1234\rangle&\mapsto[13][22][33][44]\langle5\rangle=\langle\overline{23}1\overline{45}\rangle\\ \langle3\dot{2}41\rangle=(13)(22)(34)(44)\langle1234\rangle&\mapsto[13][22][34][44]\langle5\rangle=\langle14\overline{23}5\rangle\\ \langle3412\rangle=(13)(24)(33)(44)\langle1234\rangle&\mapsto[13][24][33][44]\langle5\rangle=\langle31425\rangle\\ \langle3421\rangle=(13)(24)(34)(44)\langle1234\rangle&\mapsto[13][24][34][44]\langle5\rangle=\langle14325\rangle\\ \langle4123\rangle=(14)(24)(34)(44)\langle1234\rangle&\mapsto[14][24][34][44]\langle5\rangle=\langle43215\rangle\\ \langle41\dot{3}2\rangle=(14)(24)(33)(44)\langle1234\rangle&\mapsto[14][24][33][44]\langle5\rangle=\langle\overline{34}215\rangle\\ \langle4\dot{2}13\rangle=(14)(22)(34)(44)\langle1234\rangle&\mapsto[14][22][34][44]\langle5\rangle=\langle4\overline{23}15\rangle\\ \langle4\dot{2}\dot{3}1\rangle=(14)(22)(33)(44)\langle1234\rangle&\mapsto[14][22][33][44]\langle5\rangle=\langle\overline{234}15\rangle\\ \langle4312\rangle=(14)(23)(34)(44)\langle1234\rangle&\mapsto[14][23][34][44]\langle5\rangle=\langle24315\rangle\\ \langle4321\rangle=(14)(23)(33)(44)\langle1234\rangle&\mapsto[14][23][33][44]\langle5\rangle=\langle32415\rangle \end{aligned} Observe that the images of the nine derangements contain no sequences of consecutive elements.

Since there is a one-to-one correspondence between the set of derangements of $[n]$ and the set of permutations of $[n+1]$ that fix $n+1$ and contain no sequences of consecutive elements (we let $\overline{T}_{n+1}$ denote this set), we have $$D_n=\lvert \overline{T}_{n+1}\rvert.$$ But there is an immediate bijection between $\overline{T}_{n+1}$ and $T_n-\overline{T}_n,$ the set of elements of $T_n$ that do not fix $n.$ Therefore $$D_n=\lvert T_n-\overline{T}_n\rvert$$ and $$D_n+D_{n-1}=\lvert T_n-\overline{T}_n\rvert+\lvert \overline{T}_n\rvert=\lvert T_n\rvert.$$

• Thanks - this is a great answer! – user84413 Oct 6 '13 at 16:40
• Very nice indeed, and thank you. – Kevin P. Costello Oct 7 '13 at 17:21

Let $\sigma$ be the circular permutation $i\mapsto i+1$.

Then, you can establish a bijection $D_n\cup D_{n-1}\to T_n$ (I abuse notation for $D_n$ to design the set as well as the cardinal) by mapping any $\tau$ to $\tau\circ\sigma$,where elements of $D_{n-1}$ are naturally extended with $n\mapsto n$. It is straightforward to verify that this is a bijection.

• If I take the derangement 54123 of {1,...,5} and compose it with $\tau$, does that give the permutation 41235 (which is not in $T_n$)? – user84413 Jul 24 '13 at 20:33
• I might have misunderstood your encoding of permutations. I understood "do not have i followed by i+1" as "the image of i is never i+1". I change the answer. (But the image of 54123 was 15234) – Denis Jul 25 '13 at 0:49

EDIT: What's below is actually WRONG, due to multiple issues noted in the comments (the equation taken modulo $n$ leads to situations where a consecutive $n1$ causes problems, and it's not necessarily a bijection.

I think a variant on dkuper's argument can be made to work.

If I understand correctly, the permutations in $Q_n$ are those which satisfy $\sigma(i)+1 \neq \sigma(i+1)$ for $1 \leq i \leq n-1$. Conversely, we can think of $D_n+D_{n-1}$ as consisting of those permutations satisfying $\tau(i) \neq i$ for $1 \leq i \leq n-1$ ($D_n$ corresponds to those permutations with $\tau(n) \neq n$ as well, while $D_{n-1}$ corresponds to fixing $\tau(n)=n$).

This suggests that we construct our bijection in such a way that $\sigma(i)+1=\sigma(i+1)$ if and only if $\tau(i)=i$. The former equation can be rewritten as $i=\sigma^{-1} (\sigma(i+1)-1)$. So if we define our bijection by taking $\sigma$ to the permutation satisfying $$\tau(i)=\sigma^{-1}\left(\sigma(i+1)-1\right),$$ where addition and subtraction are taken modulo $n$, things work the way we want them to.

• Great answer! I'm not sure if in the question the addition is taken modulo, but if it is, it's finally the answer to one of my favourite questions:) – savick01 Sep 9 '13 at 19:40
• This is exactly what I tried at one point, because it looked as if this should work; but I ran into some difficulties. For example, the permutation 4132 (so $\sigma(1)=4, \sigma(2)=1$, etc) in $T_n$ maps to 1423, which is not in $D_4$; and the permutation 2413 maps to 4213, which also is not in $D_4$ (if I am computing these correctly). Also, 3214 maps to 3412, which is not in $D_3$. Maybe some modification of this will work, though, if this doesn't already. – user84413 Sep 9 '13 at 21:07
• There's actually multiple issues here (in addition to the issue you noted where I'm treating $41$ appearing consecutively as bad, $\sigma \rightarrow \tau$ isn't even a bijection!). I'm not sure what the proper etiquette in terms of deletion is, but for now I'm leaving it up with a note explaining what's wrong, and I'll eventually edit the answer if it seems fixable. – Kevin P. Costello Sep 9 '13 at 21:39
• Thanks for your response, and I don't know about the proper etiquette either. I have had to delete some of my answers to problems, since they were totally wrong; but yours is actually a pretty reasonable approach, which hopefully is fixable in some way. – user84413 Sep 9 '13 at 22:52
• @Kevin Costello It was pointed out to me that my question had been asked previously (see above), and the answer that was given before is identical to yours (although written differently). – user84413 Sep 11 '13 at 19:32