Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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.. –  anon Jun 17 '12 at 18:50
    
Your recurrence gives $a_5=(2)(1)+(4)(1)=6$, but I count 8: 13254, 13524, 13542, 14253, 14352, 15243, 15324, and 15432. –  Gerry Myerson Jun 18 '12 at 3:35
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. –  Gerry Myerson Jun 18 '12 at 3:42
    
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! –  Marc van Leeuwen Jun 18 '12 at 14:48
    
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. –  Leon Lampret Jun 19 '12 at 9:16
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
Hmm, interesting. It's good to get acquainted with a database such as OEIS, I didn't know of this before, thank you :). –  Leon Lampret Jun 19 '12 at 9:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.