Question 5
A permutation of the integers $1,2, \ldots, m$ is called fresh if there exists no positive integer $k \lt m$ such that the first $k$ numbers in the permutation are $1,2, \ldots, k$ in some order. Let $f_{m}$ be the number of fresh permutations of the integers $1,2, \ldots, m$.
Prove that $f_{n} \geq n \cdot f_{n-1}$ for all $n \geq 3$.
For example, if $m=4$, then the permutation $(3,1,4,2)$ is fresh, whereas the permutation $(2,3,1,4)$ is not.
Prove that $f_{n} \geq n \cdot f_{n-1}$ for all $n \geq 3$.
For example, if $m=4$, then the permutation $(3,1,4,2)$ is fresh, whereas the permutation $(2,3,1,4)$ is not.