Up! Up!

almost 2 years overdue but whatever We will solve this problem using recurrence relations. Let $x_n$ denote the number of ordered pairs $(b,c)$ and let $z_{n+1}$ denote the number of permutations $a$. We wish to show that \[z_{n+1} = x_n.\] Define a large cycle to be a cycle of length $\ge 2$. Define a singleton to be a cycle of length $1$; i.e. a fixed point. It's clear that when we write $b, c$ in cycle notation, $c(x) = x$ holds if $x$ is in a large cycle of $b$ and $b(x) = x$ holds if $x$ is in a large cycle of $c$. In other words, $x_n$ is equal to the number of ways to choose a permutation $d$ on $[n]$ and to label each of its large cycles with one of $\{B,C\}$. (Singletons are unlabeled.) Call these permutations special. Define special_2 permutations as those satisfying the conditions on permutation $a$. Let's find a recurrence relation on $x_i$. We do casework on $d(n)$: Case I. $d(n) = n$; i.e. $n$ is in a singleton. In this case, we can delete $n$ to yield a new special permutation $d'$ on $[n-1]$. Each $d'$ extends uniquely to a $d$. Hence the number of such $d$ is exactly $x_{n-1}$. Case II. $n$ is in a large cycle of length $\ge 3$, or $n$ is in a large cycle of length $2$ that is labeled $B$. In this case, we can delete $n$ from its cycle to yield a new special permutation $d'$. (We erase the label $B$ if necessary.) Each $d'$ extends to exactly $(n-1)$ of the $d$'s, since we can insert $n$ immediately after any of $1,2,\cdots, (n-1)$. Hence the number of such $d$ is exactly $(n-1)x_{n-1}$. Case III. $n$ is in a large cycle of length $2$ that is labeled $C$. In this case, we can delete $n$ from its cycle to yield a new special permutation $d'$ (we erase the label $C$). Each $d'$ extends to $k_{d'}$ of the $d$'s, where $k_{d'}$ denotes the number of singletons of $d'$. The number of such $d$ is exactly the sum over all $d'$ of $k_{d'}$. We switch the order of summation and find the sum over all elements $r \in [n-1]$ of $s_r$, where $s_r$ is the number of $d'$ that have a singleton at $r$. But by deleting $r$, we find that $s_r = x_{n-2}$. Hence the desired sum is actually $(n-1)x_{n-2}$. // Summing the contributions from the three cases yields \[x_n = nx_{n-1} + (n-1)x_{n-2}\]for $n \ge 3$. We evaluate $x_1 = 1$, $x_2 = 3$ as the initial conditions for the recurrence. We evaluate $z_2 = 1$, $z_3 = 3$. It remains to show that $z_{n+1} = nz_n + (n-1)z_{n-1}$ for $n \ge 4$. Consider $a$ from earlier and let $u$ be such that $a(u) = n+1$. We do casework on $a(u-1)$ and $a(u+1)$: Case I. We have $u = 1$, or $u = n+1$, or $a(u-1) + 1 \not= a(u+1)$. In this case we can define a new permutation $a'$ on $[n]$ such that $a'(x) = a(x)$ for $x < u$ and $a'(x) = a(x+1)$ for $x \ge u$. By hypothesis $a'(u-1) + 1 \not= a'(u)$, so $a'$ is special_2. Each $a'$ extends to exactly $n$ of the $a$'s, because we can ``insert'' $u$ anywhere except after ${(a')}^{-1}(n)$. Hence there are $nz_n$ such $a$ in this case. Case II. We have $2 \le u \le n$ and $a(u-1) + 1 = a(u+1)$. In this case we can define a new permutation $a'$ on $[n-1]$ such that $a'(x) = a(x)$ for $x < u-1$ and $a(x) < a(u-1)$ $a'(x) = a(x) - 1$ for $x<u-1$ and $a(x) > a(u+1)$ $a'(u-1) = a(u-1)$ $a'(x) = a(x+2)$ for $x > u-1$ and $a(x+2) < a(u-1)$ $a'(x) = a(x+2) - 1$ for $x > u-1$ and $a(x+2) > a(u+1)$ One can check that $a'$ is special_2. Furthermore, each $a'$ extends to exactly $n-1$ of the $a$'s, because any $u$ satisfying $2 \le u \le n$ will produce a correct $a$ from $a'$. Hence there are $(n-1)z_{n-1}$ such $a$ in this case. // Summing the contributions from the two cases yields \[z_{n+1} = nz_n + (n-1)z_{n-1},\]as desired. $\blacksquare$

A solution that doesn't use recurrence relations that might or might not be correct: Let $n=2015.$ Let $d_n$ denote the number of $n$-derangements. We find two bijections, mapping both things we are counting to $n+1$-derangements + $n$-derangements. 1. Counting $a$: If we map the one line notation to the canonical cycle notation, this is equivalent to counting the number of permutations where $k$ does not go to $k+1$ for any $k$. We have two cases: $n$ maps to $0$, and the rest must map to a derangement of $(1, 2, \ldots, n)$, or $n$ does not map to $0$, which means the entire ordered tuple maps to a derangement of $(0, 1, 2, \ldots, n).$ The total number of permutations $a$ is then the $d_{n+1} + d_n.$ 2. Counting $(b, c)$: Let $S$ be the set of points fixed by a certain $b.$ For $|S| > 0$, let $e$ be a new permutation, permuting elements in $S$, and sending the rest of the points according to $b$. The number of permutations $e$ is $|S| !,$ which is equal to the number of possible $c$’s. Therefore, the total number of pairs $(b, e)$ is equal to the total number of pairs $(b, c)$, both with $b$ having at least one fixed point. We have a bijection from each $e$ to an $(n+1)$-derangement, with 0 and elements in $S$ following the cycle (0 one-line-notation-of-permutation-of-$S$), and the rest of the elements permuted according to $e.$ The mentioned cycle has length greater than 1, therefore this must be a derangement (since the rest of the points are not fixed). There is a unique inverse map, since by fixing 0 as the first element in its cycle, we have a unique way of expressing the cycle. For $|S| = 0$, $b$ is a derangement of $n$ elements. There is only one possible $c,$ namely the identity, so the number of pairs where $b$ has no fixed points is $d_n$. Therefore there are $d_n + d_{n+1}$ permutations $a$, and pairs $(b, c),$ so the two are indeed equal.

@StoryScene can you explain your solution in details ?

If anyone understands StoryScene's solution can you please explain it ?