Question 31
A permutation of the numbers $1,2, \ldots, n$ is called "bad" if it contains a subsequence of 10 numbers in decreasing order, and "good" otherwise. For example, for $n=15$,
$$
15,13,1,12,7,11,9,8,10,6,5,4,3,2,14
$$
is a bad permutation, because it contains the subsequence
$$
15,13,12,11,10,6,5,4,3,2
$$
Prove that, for each $n$, the number of good permutations is at most $81^{n}$.
$$
15,13,1,12,7,11,9,8,10,6,5,4,3,2,14
$$
is a bad permutation, because it contains the subsequence
$$
15,13,12,11,10,6,5,4,3,2
$$
Prove that, for each $n$, the number of good permutations is at most $81^{n}$.