3
$\begingroup$

How can I solve the following exercise (from an exam from previous year):

Let $a_n$ denote the number of cycles $\pi\!=\!(\pi_1,\ldots,\pi_n)\!\in\!S_n$, such that $\pi_i\!+\!1 \neq \pi_{i+1}(\!\!\!\mod n)$ for $i\!=\!1,\ldots,n$. For example, $a_4\!=\!1$, since $(1432)$ is the only such cycle. Compute $a_n$.

My attempt: Let's say that $\pi$ is bad at $i$ if $\pi_i\!+\!1 = \pi_{i+1}(\!\!\!\mod n)$, and it is good if it is not bad at any $i$. Denote $A_n\!:=\!\{\pi\!\in\!S_n; \pi\text{ is good}\}$, so $a_n\!=\!|A_n|$. Each $\pi\!\in\!A_n$ is obtained from either some $\alpha\!\in\!A_{n-1}$ (by inserting $n$ at any of the $n\!-\!1$ places except after $n\!-\!1$ or before $1$, which gives $n\!-\!3$ choices), or from some $\beta\!\in\!B_{n-1}\!:=\!\{\pi\!\in\!S_n; \pi\text{ is bad at precisely one place}\}$ (by inserting $n$ in the middle of the bad place, which gives one choice). Thus for $b_n\!:=\!|B_n|$, we have $a_n=(n\!-\!3)a_{n-1}\!+b_{n-1}.$ Now, what is $b_n$? Each $\pi\!\in\!B_n$ can be transformed so that it is bad at $(\ldots n,1\ldots)$, namely if $\pi$ is bad at $(\ldots\pi_k,\pi_{k+1}\ldots)$, we replace each $\pi_i$ by $\pi_i\!+\!n\!-\!\pi_k (\!\!\!\mod n)$. This transformation sends $n$ different cycles to the same one, which proves $b_n\!=\!na_{n-1}$. Therefore $a_n=(n\!-\!3)a_{n-1}\!+(n\!-\!1)a_{n-2},$ with $a_3\!=\!a_4\!=\!1$. Now I don't know what to do, since this is a linear homogenous difference equation with nonconstant coefficients.

Question: Is this recursion correct? How can I solve the exercise?

  • 0
    Gerry: Yes, you are right, thanks for noticing. @Marc: Hehe, no, that was just me changing "." to "!" to make it imperative, but I didn't think it could cause confusion with the factorial. I'll change it back, thanks.2012-06-19

1 Answers 1

4

This may be a problem that was harder than the examiners thought it would be. It seems to be Number of cyclic permutations of [n] with no i->i+1 (mod n) from OEIS. There you'll find the recurrences, $a_n = (n-2)a_{n-1} + (n-1)a_{n-2} - (-1)^n$ and $a_n = (n-3)a_{n-1} + (n-2)(2a_{n-2} + a_{n-3})$ as well as the formula, $a(n) = (-1)^n + \sum_{k=0}^{n-1}(-1)^k{n\choose k}(n-k-1)!$ and a generating function and some references to the literature.

  • 0
    Hmm, interesting. It's good to get acquainted with a database such as OEIS, I didn't know of this before, thank you :).2012-06-19