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?

  • 2
    I haven't checked your reasoning, but linear recursion equations with polynomial coefficients can be solved (at least implicitly) with generating functions and differential equations..2012-06-17
  • 0
    Your recurrence gives $a_5=(2)(1)+(4)(1)=6$, but I count 8: 13254, 13524, 13542, 14253, 14352, 15243, 15324, and 15432.2012-06-18
  • 2
    The first problem is that inserting $n$ in the middle of the bad place may not work: inserting 5 in the middle of the bad place of 1324 gives 13245, which is still bad. The second problem is you miss the insertion of $n$ away from the middle of the bad place, e.g., 1324 gives rise to 15324 and 13524 and 13254.2012-06-18
  • 0
    How come there is an exclamation mark at the end of the question? This looks like they are asking for the factorial of $a_n$ rather than for $a_n$; not a good thing to do in an exam!2012-06-18
  • 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