Let $f(n)$ be the number of such permutations and we know that $f(1)=1$ and $f(2)=2$. Suppose we have a permutation that satisfies given conditions and $a_k =1$. Note that all numbers that are greater than $k$ are not in $\{a_1, \ldots, a_{k-1}\}$. It follows that $\{2, \ldots, k\} = \{a_1, \ldots, a_{k-1}\}$. Pick number $k$, the only place in the subpermutation $(a_1, \ldots, a_{k-1})$ where it can be placed is $a_1$; otherwise if $a_i=k$, then $k+i = k+a_i \leq a_k+k = k+1$, a contradiction. Hence $a_1= k$ and inductively we can prove that $a_{i} = k+1-i$ for $i \in [1,k]$. Therefore if $a_k=1$, then our permutation must be of the form $(k, \ldots, 1, a_{k+1}, \ldots, a_n)$. Observe that given conditions for numbers in subpermutation $(a_{k+1}, \ldots, a_n)$ are equivalent to conditions that $(a_{k+1}-k, \ldots, a_n-k)$ satisfy. Since $\{a_{k+1}-k, \ldots, a_n-k\}$ = $\{1, \ldots, n-k\}$, we get that there are $f(n-k)$ such permutations. Summing over all possible position of $1$ in the permutation, we obtain a recursive formula: \[f(n)= f(n-1)+f(n-2)+ \cdots + f(1) +1,\] yielding by induction $f(n)=2^{n-1}$.

Consider the numbers $1,2,3,4,\ldots,n$ in increasing order. Between every pair $i,i+1$ (for $i=1,\ldots,n-1$) we may put a cutting point (or not). Then we cut the sequence at the chosen cutting points, and we flip over each of the resulting pieces. (*) A permutation satisfies the condition of the problem if and only if it can be produced by such a cutting process. Since there are $n-1$ possible cutting points, this yields the answer $2^{n-1}$. Question: Is there an easy and direct argument for (*)?

Here are other characterizations of the permutations manuel153 describes: they are those that avoid the permutation patterns 231 and 312. In other words, if our permutation has the form $\cdots a\cdots b\cdots c\cdots$ then it must not be the case that $b>a>c$ nor $a>c>b$. Equivalently, if the permutation has the form $\cdots a\cdots b\cdots $ with $a>b$, every entry whose value is between $b$ and $a$ must lie between $a$ and $b$ in the permutation. Possibly one can use one of these characterizations to get your claim directly.

This is my solution to the problem:

I will prove such a permutation is equivalent to a sequence of $n-1$ letters $S$ or $B$ (basically, $S$ means "go up" and $B$ means "go down"). Define $f(i)=a_i$ and graph this function. We will call this the "drawing". Clearly each permutation is equivalent to a drawing where no segment has slope $ < -1$, and no value is repeated. To each permutation I assign a sequence of letters. There are $n-1$ segments in a drawing. If a segment has positive slope, write $S$, otherwise write $B$. For example, $1,4,3,2,5$ is equivalent to $SBBS$. Now, suppose we have a sequence of $n-1$ letters $S$ or $B$. Note that each letter $S$ (say it corresponds to segment $A\rightarrow C$) should represent a maximum of the drawing (a "maximum" is a point that is greater than all previous points). This is because, if it didn't, there would be a previous point that is greater than this point ($C$), and so to "go down" form that previous point to $A$, since we can only decrease by $1$ (because of the rules), we would have to attain the value $C$ twice. With this in mind, say $K_1$ is the length of the final block of $B$'s (possibly $0$). So draw the drawing "backwards", starting with the final point $=n-K_1$, and going up in reverse $K_1$ times until you reach a point with value $n$ (this must be the case, since the final $S$ letter must be a global maximum). Now, ignore all points with values $\ge n-K_1$. erase the final $K_1+1$ letters from your string, and repeat the process. It is easy to see the process draws a correct drawing, and a correct drawing must be attained by applying the process to its correspondent sequence of letters. So the set of strings, the set of drawings and the set of correct permutations are all equivalent through a bijection. So there are $2^{n-1}$ permutations in total. I like this solution because it doesn't involve induction. With induction, the problem becomes easier but more boring.

These posts all look super overkill for a Q1. Let $\phi(n)$ denote the given number. Just suppose that $k$ is the location, where $n$ is assigned, namely, $a_k=n$. For $a_k+k = n+k \leq a_{k+1}+k+1$ gives us, $a_{k+1}\geq n-1$, hence is $n-1$. For $k+2$, $n+k\leq a_{k+2}+k+2\implies a_{k+2}\geq n-2$. Since, $n-1$ and $n$ are already used, we have, $a_{k+2}=n-2$, and proceeding in this way, $a_{k+i}=n-i$, for every $i=1,2,\dots,n-k$. Now, just note that, if $i\leq k-1$; and $j\geq k$, then, $a_i+i\leq a_j+j$ is trivially satisfied. Hence, once we fix the location of $n$, to $k$; the total number is just the number of arrangements, over $\{1,2,\dots,k-1\}$ (since, $(a_1,\dots,a_{k-1})$ is a permutation of $\{1,2,\dots,k-1\}$). Hence, $$ \phi(n)=\sum_{i=0}^{n-1} \phi(i), \quad \phi(0)=\phi(1)=1, $$giving us $2^{n-1}$ such arrangements.

here's a different solution let $S_n$ the set of such permutaion and let $|S_n|=f(n)$ notice that $f(n)=2^{n-1}$ we will give a bijective map that send the set of subset of ${1,2....n-1} $ to $S_n$ the map is as follow ${a_1,a_2....a_n}$ then if $a_i > a_j $ for $j>i$ we will circle $a_i$ then we will insert the element that have a circle to a set $T$ it's obvious that $T $ is a subset of ${1,2....n-1}$ and it's easy to see that the map is bijective

Let $f(n)$ be the number of permutations that satisfy the conditions for the set $\{1,2,\dots ,n\}$. Let $a_k = n$. If $k\neq n$ , then we must have $a_{k+1} = n-1 , a_{k+2} = n-2 , ... , a_n = k$. If $k\neq 1$ , then we are left with the set $\{1,2,\dots , k-1\}$ where the condition is the same. If $k=1$, then there is only $1$ possible permutation. Finally if $k=n$, then we are left with the set $\{1,2,\dots , n-1\}$ where the condition is the same. So we get $f(1)=1$ and for all $n\geq 2$, $f(n)=1 + \sum_{k=1}^{n-1} f(k)$. And by a simple induction we get $f(n)=2^{n-1}$, yielding the result $f(2014) = 2^{2013}$ for our case.

$$x_{n+1}= 1+ x_1+x_2+...+ x_n$$$$x_n= 2^{n-1}$$

The answer is $\boxed{2^{2013}}$. Let $f(n)$ be the number of permutations of $(1,2,\ldots, n)$ such that for all $1 \le i <j \le n$, we have $i + a_i \le j + a_j$. Note that the condition is equivalent to $a_{i+1} \ge a_i - 1$ for each $1 \le i \le n - 1$. Claim: $a_i = a_1 - (i - 1) \forall i \in [1, a_1 ]$. Proof: Suppose this wasn't the case. Then there exists an integer $c \in [1,a_1]$ with $a_c > a_1$ (because if not, then inductively $a_i = a_1 - (i - 1)$ is forced to happen for $i \in [1,a_1]$). However, note that for any $i$, if $a_i > a_1$, then $a_{i + 1} \ge a_i - 1 \ge a_1$, but since $a_{i+1} \ne a_1$, $a_{i + 1 }> a_1 $ also. This implies that $a_1, a_2, \ldots, a_{c - 1}$ are the only values in the sequence less than or equal to $a_1$. However, the sequences takes all values in $[1,a_1 ]$, so $c - 1 \ge a_1 \implies c \ge a_1 + 1$, a contradiction. $\square$ Claim: $f(n) = 1 + f(1) + f(2) + \cdots +f(n-1)$ for any $n > 1$. Proof: We do casework on $a_1$. Let $a_1 = k$. We have $a_i = k - (i - 1)$ for all $i$ in $[1, k]$. But then $(a_{a_1 + 1}, a_{a_1 + 2} , \ldots, a_n)$ is a permutation of $(a_1 + 1, a_1 + 2, \ldots, a_n)$. So if $k < n$, the number of ways to make this is just $f(n - k)$, and if $k = n$, it's just $1$. Summing up, we have a total of $1 + f(1) + f(2) + \cdots + f(n-1)$, as desired. $\square$ Claim: $f(n) = 2^{n-1}$ for all $n$. Proof: This is done by induction. The base case $n = 1$ is obvious. If it's true for $1, 2, \ldots,n - 1$, we have $f(n) = 1 + 2^0 + 2^1 + \cdots + 2^{n-2} = 2^{n-1}$, as desired. $\square$ Thus, $f(2014) = 2^{2013}$, and we are done.