I would accept Sam's and lambda's comments as the answer. For the record, I'll just flesh it out a bit for the first formula.
In terms of compositions of $n$, the following is all but self-evident
$$a_n = \sum_{n_1+n_2+\ldots+n_k=n} \binom{n}{n_k}\binom{n-n_k}{n_{k-1}}\binom{n-n_k-n_{k-1}}{n_{k-2}}\ldots \binom{n-n_k-n_{k-1}-n_{k-2}-\ldots-n_2}{n_1}$$
where the sum is over all compositions of $n$. Now define a mapping from the compositions of $n$ to the permutations $\sigma$ with $\sigma(i) \le i+1$ for $1 \le i \le n$ as follows: Map composition $n_1+n_2+\ldots+n_k = n$ to
\begin{align}
\sigma(n_1) &= 1\\
\sigma(n_1+n_2) &= n_1+1\\
\sigma(n_1+n_2+n_3) &= n_1+n_2+1\\
&\ldots\\
\sigma(n_1+n_2+\ldots+n_k) &= n_1+n_2+\ldots+n_{k-1}+1\\
\sigma(i) &= i+1\ \text{for}\ i \not\in \{n_1,n_1+n_2,\ldots,n_1+n_2+\ldots+n_k\}
\end{align}
After checking this mapping is indeed a 1-1 correspondence between the compositions of $n$ and the permutations $\sigma$ with $\sigma(i) \le i+1$, we can now rewrite
\begin{align}
&\binom{n}{n_k}\binom{n-n_k}{n_{k-1}}\binom{n-n_k-n_{k-1}}{n_{k-2}}\ldots \binom{n-n_k-n_{k-1}-n_{k-2}-\ldots-n_2}{n_1} = \\
&\binom{n_1+n_2+\ldots+n_k}{n_k}\binom{n_1+n_2+\ldots+n_{k-1}}{n_{k-1}}
\binom{n_1+n_2+\ldots+n_{k-2}}{n_{k-2}}\ldots \binom{n_1}{n_1} =\\
&\binom{n_1+n_2+\ldots+n_k}{n_1+n_2+\ldots+n_{k-1}}
\binom{n_1+n_2+\ldots+n_{k-1}}{n_1+n_2+\ldots+n_{k-2}}
\binom{n_1+n_2+\ldots+n_{k-2}}{n_1+n_2+\ldots+n_{k-3}}\\
&\ldots\binom{n_1}{0}=\\
&\binom{n_1+n_2+\ldots+n_k}{\sigma(n_1+n_2+\ldots+n_k)-1}
\binom{n_1+n_2+\ldots+n_{k-1}}{\sigma(n_1+n_2+\ldots+n_{k-1})-1}\\
&\binom{n_1+n_2+\ldots+n_{k-2}}{\sigma(n_1+n_2+\ldots+n_{k-2})-1}
\ldots \binom{n_1}{\sigma(n_1)-1} = \prod_{i=1}^n \binom{i}{\sigma(i)-1}
\end{align}
The more general formulas follow by noticing that the mapping from compositions to permutations described above is a bijection between compositions with exactly m ones and permutations with exactly m fixed points.