If $P(n, m)$ is the number of permutations such that $m$ is the first fixed point, prove that $P(n, m + 1) = P(n, m) - P(n - 1, m)$

Question

For $n, m \in \mathbb{N}, m \leq n$, let $P(n, m)$ denote the number of permutations of length $n$ for which $m$ is the first number whose position is left unchanged. Thus, $P(n, 1) = (n - 1)!$ and $P(n, 2) = (n - 1)! - (n - 2)!$. Show that $$P(n, m + 1) = P(n, m) - P(n - 1, m)$$ for each $m = 1, 2, \cdots, n - 1$.

Hello, can someone help me with the combinatorial proof for this?

I can prove it in other way, by proving that $$P(n, m) = \sum_{i = 0}^{m - 1}(-1)^i\binom{m-1}{i}(n - i-1)!$$ using PIE. Now, turning $P(n, m) - P(n - 1,m)$ into $P(n, m+1)$ is just algebraic manipulation.

I'd be thankful if someone could help in proving this combinatorially.

Thanks

Answer 1

Fact. $\displaystyle P(n,m)=\sum_{k=m}^{n-1}P(n-1,k)$.

Using the fact we get that $\displaystyle P(n,m+1)=\sum_{k=m+1}^{n-1}P(n-1,k)$. Subtracting these two equations we get $P(n,m)-P(n,m+1)=P(n-1,m)$.

Proof of the fact. Take any permutation from $P(n,m)$ and remove $m$-th element from the set. Then we get the permutation of the $n-1$ elements such that the first fixed point is on the $m$-th place or further.

Answer 2

Take the permutations in $P(n,m)$ and do two swaps: $m$ with $m+1$ and then $m+1$ with whatever is in $m+1$-th position. This has $m+1$ fixed, and anything before not fixed with the exception of only $m$ that may still be there. The permutations with fixed $m$ and $m+1$ and nothing before are exactly $P(n-1,m)$.