Prove that for $n>0$ number of permutations of set $\{1,...,n\}$ such that $a_{i+1}-a_i \neq 1$ for every $i=1,2,..,n-1$ is equal to $$D_n + (n-1)D_{n-2} + (-1)^{n-1} $$
where $D_n$ is number of disorders.
Could you give me a hint ?
Asked
Active
Viewed 73 times
1
-
Could you let us know how this question came to you? and how much you know about permutations and about recurrences and about induction and about $D_n$? – Gerry Myerson Sep 07 '14 at 00:17
1 Answers
0
$\text{Hint:}$
Try letting $E_{i}$ be the set of permutations which have $a_{i+1}-a_{i}=1$ for $1\le i\le n-1$, and then use Inclusion-Exclusion to find $|E_{1}^{c}\cap\cdots\cap E_{n-1}^{c}|$.
user84413
- 27,211
-
Ok, So Let $E_1$ - number of permutation such that we have "12". Then $|E_1| = (n-1)(n-2)!$ And $|E_{n-1}| = (n-1)(n-2)!$. When we have $|E_i\cap E_{i+1}| = (n-2)(n-3)!$. But what in other cases ? For example $E_1\cap E_4\cap E_6 $ ???? – xawey Sep 07 '14 at 10:02
-
To find $|E_i|$, you can think of i and i+1 as glued together, so then $|E_i|=(n-1)!$ since you are permuting n-1 objects. Similarly, $|E_i\cap E_j|=(n-2)!$, since you are gluing i and i+1 together and j and j+1 together and so are permuting n-2 objects. You might also find it useful to use the recurrence relation $D_n=nD_{n-1}+(-1)^n$. – user84413 Sep 07 '14 at 19:57