Permutation question based on recursion

Question

Let $a_1,a_2,\ldots,a_n$ be a permutation of the numbers $1,2,\ldots,n$ such that $\forall 1 \leq k \leq n-1$, $ \quad a_1,a_2,\ldots a_k$ is NOT a permutation of $1,2,\ldots,k$. Determine the number of permutations possible.

I first noted that for n=1, no permutations exist and for n=2 one such permutation exists . I tried to create a recursion relation, somewhat like principle of inclusion and exclusion but I kept getting it incorrect (It didn't satisfy for small values of n).

Answer 1

HINT

Lets call a permutation with this property good, and a permutation without this property bad.

By definition, any bad permutation $\pi$ has some $k$ where $a_1, \dots, a_k$ is a permutation of $1, \dots, k$. This also means there is a smallest such $k$ for this $\pi$, which we will call $\pi$'s badness number.

• How many bad permutations of size $n$ has a badness number of $k$?

Can you finish from here? Remember to check your answer against http://oeis.org/A003319 as @saulspatz suggested.