Un problema complicado en las permutaciones

Question

Supongamos que $x_1, x_2, ......, x_{10}$ es una permutación de $1, 2, ......, 10$ .

Para $1 \leq m < n \leq 10$ Tenemos $x_m+m \leq x_n+n$ .

Intenta encontrar el número de esas permutaciones.

Podemos encontrar que la desigualdad es equivalente a: $$x_n-1 \leq x_{n+1}$$ pero no puedo llegar más lejos.

¿Alguien tiene alguna idea?

Answer 1

Generalizar el problema para cualquier $k$ en lugar de $10$ . Llama a una permutación $x=(x_1, \dots , x_k)$ de los números $1, \dots , k$ disminuyendo lentamente si $x_n-1 \le x_{n+1}$ para cada uno $1 \le n \le k-1$ . Deje que $SD_k$ ser el conjunto de todas las permutaciones de números que disminuyen lentamente $1, \dots , k$ y $s_k=|SD_k|$ .

Deje que $x \in SD_k$ . Si $x_n=k$ entonces la desigualdad implica consecutivamente que $x_{n+i}=k-i$ para cada uno $i \le 1$ de tal manera que $n+i \le k$ . Luego $(x_1, \dots , x_{n-1}) \in SD_{n-1}$ . Esto nos da una fórmula recurrente $$s_k= \sum_ {n=1}^n s_{n-1},$$ donde ponemos $s_0=1$ .

Así, $s_k-s_{k-1}= s_{k-1}$ para cada uno $k \ge 2$ . La simple inducción muestra que $s_k=2^{k-1}$ para cada uno $k \ge 1$ .