Permute 1~10 with $x_m+m \leq x_n+n$ for $1\leq mSuppose that $x_1,\cdots,x_{10}$ is a permutation of 1~10 while
$$x_m+m\leq x_n+n, \forall 1\leq m <n\leq 10.$$
Question: How many such permutations $(x_1,\cdots,x_{10})$ are there?

I can only do this by examining smaller cases such as 1~2, 1~3 and 1~4, then find that the answer is $2^{N-1}$ when permuting 1~N. I wonder whether there is a rigid mathematical induction of this problem rather than a guess.
 A: As both comments from @ PM 2Ring and @ Michael Lugo said, we can use induction to show that each "good" permutation of n to two good permutations of n+1.
Let $f(N)$ denote the number of possible permutations $x_1, \cdots, x_N$ of $[N]$ s.t.
\begin{align}
x_m+m\leq x_n+n, \forall 1\leq m <n\leq 10 \tag{1}\label{eq:cond}
\end{align}
and let $P(N)$ denote the set of such permutations.
When $N = 2$, clearly $f(N) = 2$.
How can we proceed $N \rightarrow N + 1?$
What are the possible positions of this "new" element $N+1$?
Let $i(k)$ denote the index of $k$ in the permutation, we need to have
$$x_{i(N+1)} + {i(N+1)} = N + 1 + i(N + 1) \leq x_{i(N+1) + 1} + {i(N+1) + 1},$$
which gives
$$N \geq x_{i(N+1) + 1}.$$
This implies that if $N + 1$ is not inserted in the last position, then it must be inserted exactly before $N$.
When inserted in the last position.
For each permutation $\pi \in P(N)$, we can simply add $N + 1$ at the end to get a new permutation $\pi'$ of $[N+1]$ and it is easy to check that $(1)$ is satisfied. This case provides $f(N)$ possible permutations.
When inserted exactly before $N$.
We claim that if the new permutation after the insertion satisfies $(1)$, then the permutation before this insertion must satisfy $(1)$, and thus this case gives another $f(N)$ possible permutations.
Let $x_1, \cdots, x_N$ be the permutation before the insertion, where $x_i = N$ for some $i \in [N]$, after the insertion, it becomes
$$x_1, x_2, \cdots, x_{i-1}, N + 1, x_i = N, x_{i+1}, x_{i+1}, \cdots, x_N.$$
Suppose that there exist $1 \leq m < n \leq N$ s.t. $x_m + m > x_n + n$ before the insertion.
Recall that we need that
$$x_1, x_2, \cdots, x_{i-1}, N + 1, x_i = N, x_{i+1}, x_{i+1}, \cdots, x_N$$
satisfies $(1)$.
Clearly, we should have that $(1)$ holds for $1 \leq m < n \leq i - 1$ and for $i \leq m < n \leq N$.
So now the only remaining possibility is that $x_m + m > x_n + n$ for some $1 \leq m \leq i - 1 < n \leq N$, which gives
$$x_m + i - 1 \geq x_m + m > x_n + n \geq x_i + i = N + i$$
since $m \leq i-1$ and $i \leq n$.
This requires that $x_m > N + 1$, which is impossible, completing the proof by contradiction.
Now we conclude that $f(N+1) = 2f(N)$, which gives $f(N) = 2^{N-1}$ together with $f(2) = 2$.
A: Hm, the problem can be read as $x_n \geq x_m - (n - m)$. It is easy to see that this is exactly the case if two consecutive values are either monotonic of if they fall by exactly $1$, so $x_{m+1} > x_m$ or $x_{m+1} = x_m - 1$. Thus the permutation can be split into monotonic rising subsequences that stepwise descend by 1. Example for $N=5$: $0,3,2,5,4$.
So the question is: How many ways exists to do this? Note that if you split $1:N$ into such subsequences there is exactly one way to arrange them in this way. So the question becomes: How many ways are there to do this?
Clearly this number follows the recurrence:
$$ \nu(N) = \nu(0) + \nu(1) + \ldots + \nu(N-1)$$
(corresponding to the possibilities if the first one is $[1:N],\,[1:N-1],\,\ldots,\,1$), with $\nu(0) = 1$.
Thus $\nu(N) - \nu(N-1) = \nu(N-1)$ (unless $N=1$, for which $\nu(1) = \nu(0)$) and thus $\nu(N) = 2\nu(N-1) = 2^{N-1}\nu(1) = 2^{N-1}$. QED
