Let $F(m,n)$ to be the number of ways to arrange the integers $1,2,\dots,n$ in a row such that the number of times that an integer is bigger than the previous integer is $m$.
Find a recurrence relation for $F(n,m)$
My attempt:
Let's look at the position of the integer $n$, there are $4$ options for it:
- It's last in the row, therfore if we take it out, we remain with $F(n-1,m-1)$
- It's first in the row, therfore if we take it out, we remain with $F(n-1,m)$
- It's in between two numbers which are in ascending order, therfore if we take it out, we remain with $F(n-1,m)$
- It's in between two numbers which are in descending order, therfore if we take it out, we remain with $F(n-1,m-1)$
Hence,
$F(n,m)=2\cdot F(n-1,m)+2\cdot F(n-1,m-1)$
But it is not the right answer.
Where is my mistake? Thanks in advance.
In options $3$ and $4$ there are many places where the neighboring numbers are in that order, so there should be a coefficient involving $m$. Think of the number of places to add $n$ in.
For $3$, there are $m$ places you can insert $n$. For $4$ there are $n-m-2$ places to insert $n$, so the recurrence should be $$F(n,m)=(m+1)F(n-1,m)+(n-m)F(n-1,m-1)$$