MathDB

A permutation of the integers

1, 2, \ldots, m

is called fresh if there exists no positive integer

k < 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 \ge n \cdot f_{n - 1}

for all

n \ge 3

.
For example, if

m = 4

, then the permutation

(3, 1, 4, 2)

is fresh, whereas the permutation

(2, 3, 1, 4)

is not.

4