# Permute 1~10 with $x_m+m \leq x_n+n$ for $1\leq m<n \leq 10$ [duplicate]

Suppose that $$x_1,\cdots,x_{10}$$ is a permutation of 1~10 while $$x_m+m\leq x_n+n, \forall 1\leq m 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.

• I expect there's a clever induction proof. Each new number doubles the number of valid permutations. There are tantalising patterns in the sequences of $x_m+m$. Here's a brute-force demo in Python; it gets slow for $n=10$. sagecell.sagemath.org/… Commented Aug 23, 2022 at 14:07
• I would suspect there is a way to take each "good" permutation of $n$ to two good permutations of $n+1$. Commented Aug 23, 2022 at 14:24
• I upvoted both the question (for showing in my opinion substantial work because induction on the length is a natural thing to try) and the answer. But, it still looks like a duplicate. Approach0 is a good tool for locating duplicate candidates. Commented Aug 24, 2022 at 4:40

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 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$$.

• Here's a recursive generator in Python of this algorithm. Commented Aug 24, 2022 at 10:25
• sagecell.sagemath.org/… Commented Aug 24, 2022 at 10:26

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