2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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)!$

$\endgroup$
  • $\begingroup$ You missed the fact that you could place $k+1$ into an invalid permutation, breaking up the only pair that made it invalid. For instance, for $n=3$, there is $1,3,2$ in addition to the two permutations you counted. $\endgroup$ – joriki Apr 7 '16 at 6:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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