Restrictions of Inserting Numbers Method These are two similar questions from two different contests.

*

*(AIME 2015) Call a permutation $a_1, a_2, ..., a_n$ quasi-increasing if $a_k \leq a_{k+1} + 2$ for each $1\leq k\leq n-1$.
For example, $54321$ and $14253$ are quasi-increasing permutations of the integers $1, 2, 3, 4, 5$, but
$45123$ is not. Find the number of quasi-increasing permutations of the integers $1, 2, . . . , 7$.

By inserting numbers one by one, the answer is $486$, which is the intended answer.
Let me explain the method used here:
Assume that the number of quasi-increasing permutations of the integers $1, 2, 3, ..., n$ be $A_n$, then obviously $A_1=1$, $A_2=2$, $A_3=6$, thus 4 can be inserted into the string of integers $1, 2, 3$ in only $3$ ways, so $A_4=3\times A_3=18$, and so do $5, 6, 7$, so $A_7=3\times 3\times 3\times A_4=486$



*(SMO 2010 Open R1) Find the number of permutations $a_1a_2a_3a_4a_5a_6$ of the six integers from $1$ to $6$ such that for all $i$ from $1$ to $5$, $a_{i+1}$ does not exceed $a_i$ by $1$.

By inserting numbers one by one, the answer is $120$, which is not the intended answer.
By Inclusion-Exclusion, the answer is $309$, which is the intended answer.
I would like to ask what are the restrictions of this method for solving these similar problems?
 A: In general, for $n$-step process where the first step can be done in $m_1$ ways, the second in $m_2$ ways, and so on up the the $n^\text{th}$ being doable in $m_n$ ways, the number of ways to complete the whole process is $$m_1\times m_2\times \dots \times m_n$$
Importantly, the number of ways to complete each step must not depend on which particular choices you made previously. If $m_3=7$ (say), there should always be three choices for the third step, regardless of what you chose in steps $1$ and $2$.
Let's see why this works for the AIME 2015 problem. A permutation can be built by inserting the numbers $1,2,\dots, n$ one at a time. $1$ can be inserted in one way, $2$ in two ways, $3$ in three ways. For each $k\in \{4,\dots,n\}$, when you try to insert $k$ into the previous permutation made up $\{1,\dots,k-1\}$, there are always three options: either at the end of the permutation, or just before $k-1$, or just before $k-2$. These are indeed always legal, regardless of the specific ordering of $\{1,\dots,k-1\}$, and no other options are allowed. We conclude that the number of ways is $1\times 2\times 3\times 3\times \dots \times 3=2\cdot 3^{n-2}$.
Why does this same idea not work for the SMO 2010 problem? Let's see. Just look at a small example, permutations of length $3$. There is only one valid permutation of length $2$ where $a_{k+1}\neq a_k+1$, namely $[2,1]$. There are two ways to insert $3$ into this while maintaining the property $a_{k+1}\neq a_k+1$, which would suggest that there are only two valid permutations of length $3$, namely $[3,2,1]$ and $[2,1,3]$. However, there is actually a third permutation that works, namely, $[1,3,2]$. How did we miss this? The problem is that our process would require first inserting $2$ after $1$, which seems illegal, then later inserting $3$ after $1$. Inserting the $3$ blocks the $2$ from the $1$, so the it turned out not be an illegal move. To summarize,

the number of available moves depends on what choices were made later.

This shows that the number of moves at each step is not constant, so you cannot just multiply the number of ways to complete each step.
