Solution:

Consider any permutation of $1,2, \ldots, n$. Let the "height" of a number $i$ in the permutation be the length of the longest decreasing subsequence ending in $i$. Then, the permutation is bad if and only if some number has height at least 10. Also note that all numbers with the same height must be arranged in increasing order. To see that this is so, suppose that two numbers $i, j$ both have height $h$, where $i<j$, but $j$ precedes $i$ in the permutation. Then there exists a decreasing subsequence of the permutation having length $h$, ending in $j$. By attaching $i$ to the end of this, we get a decreasing sequence of length $h+1$ ending in $i$; this contradicts the assumption that $i$ had height $h$.

Now we know that, in any good permutation, every number has a height in the range $1,2, \ldots, 9$. We also know that, for each height $h$, the numbers with height $h$ occur in the permutation in increasing order. This means that, if we know which of the numbers $1,2, \ldots, n$ have height $h$ and which positions in the permutation are occupied by numbers of height $h$ for each $h=1,2, \ldots, 9$, we can uniquely reconstruct the permutation from this information. Since every possible good permutation can be represented in this form, the number of good permutations is at most equal to the number of possible assignments of heights $1,2, \ldots, 9$ to the $n$ numbers and the $n$ positions in the permutation. There are $9^{n}$ ways of assigning heights from this range to $1,2, \ldots, n$, and another $9^{n}$ ways of assigning heights to the $n$ positions; altogether this makes for at most $\left(9^{n}\right)^{2}=81^{n}$ possible good permutations.