Counting permutations with given condition

Question

I need to find number of permutations $p$ of set $\lbrace 1,2,3, \ldots, n \rbrace$ such for all $i$ $p_{i+1} \neq p_i + 1$.

I think that inclusion-exclusion principle would be useful. Let $A_k$ be set of all permutation that for every permutation $a$ in this set $a_{k+1} \neq a_k + 1$. So our answer would be $| A_1 \cap A_2 \cap \ldots \cap A_n |$. Could you help me with completing the proof?

Answer 1

I would recommend initially counting the set of all of those permuttations and then using inclusion-exclusion on this set by systematically removing the sets $B_k$ which we can define as the set of all permutations where $p_k = p_k+1$. I.e. We can account for the set of all permutations as $$|S| = n!,$$ and count each $A_k$ given that there are $n-1$ options of $p_k$ and $n-2$ free variables left as $$|A_k| = n-1 \times (n-2)! = (n-1)!.$$ Performing inclusion-exclusion by using the $A_k$'s as removal sets should follow cleanly.

Answer 2

I believe an induction proof might work nicely.

The base case $ n=1 $ is easy enough, so consider the step from $ n=k $ to $ n=k+1 $:

Of the $ k+1 $ gaps you could place the number $ k+1 $, only one will be illegal (immediately after $k$). So we get $|A_{k+1}|=k|A_k|$, $|A_1|=1$

It doesn't take long to generate $|A_n|=(n-1)!$

Answer 3

We can complete Penitent's induction argument as follows:

Denote the number of valid permutations of $k+1$ elements by $a_k$. There are two ways to generate a valid permutation of $k+1$ elements from a permutation of $k$ elements: Either by inserting $k+1$ into a valid permutation of $k$ elements at any of the $k+1$ gaps except the one behind $k$; this yields $ka_k$; or by inserting $k+1$ into a single consecutive pair that made the permutation invalid, thus making it valid. Each permutation of $k$ elements with a single consecutive pair corresponds to exactly one valid permutation of $k-1$ elements obtained by merging the pair and suitably renumbering the remaining elements. This yields a contribution $(k-1)a_{k-1}$, since each of the $k-1$ elements in each of the $a_{k-1}$ valid permutations of $k-1$ elements can be expanded into a pair. Thus we have the recurrence relation

$$ a_{k+1}=ka_k+(k-1)a_{k-1} $$

with the initial values $a_1=a_2=1$. We can rearrange the recurrence relation

$$!(k+2)=(k+1)(!(k+1)+!k)$$

for the number $!k$ of derangements of $k$ elements to

$$ \frac{!(k+2)}{k+1}=k\frac{!(k+1)}k+(k-1)\frac{!k}{k-1}\;. $$

This is our present recurrence relation with $a_k=\frac{!(k+1)}k$, and the initial values coincide, so this is a "closed form" for $a_k$, though since the number of derangements is usually counted using inclusion-exclusion, it's not really more "closed" than what you'd get directly using inclusion-exclusion in the way Rob outlined.

I posted this new question asking for a combinatorial proof of the count $a_k=\frac{!(k+1)}k$.

By the way, this is OEIS sequence A000255, shifted by one.