5. There are 10 ! permutations $s_{0} s_{1} \ldots s_{9}$ of $0,1, \ldots, 9$. How many of them satisfy $s_{k} \geq k-2$ for $k=0,1, \ldots, 9$ ?
5. Ans: 13122

Construct the permutation from the end. There are 3 choices each for $s_{9}, s_{8}, \ldots, s_{2}$ and 2 choices for $s_{1}$ and 1 choice for $s_{0}$. So the answer is $2.3^{8}=13122$.