3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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/… $\endgroup$
    – PM 2Ring
    Commented Aug 23, 2022 at 14:07
  • 2
    $\begingroup$ I would suspect there is a way to take each "good" permutation of $n$ to two good permutations of $n+1$. $\endgroup$ Commented Aug 23, 2022 at 14:24
  • $\begingroup$ 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. $\endgroup$ Commented Aug 24, 2022 at 4:40

2 Answers 2

3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Here's a recursive generator in Python of this algorithm. $\endgroup$
    – PM 2Ring
    Commented Aug 24, 2022 at 10:25
  • $\begingroup$ sagecell.sagemath.org/… $\endgroup$
    – PM 2Ring
    Commented Aug 24, 2022 at 10:26
0
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .