嘿，这个问题挺有意思的，我们可以从小例子入手找规律，再推导递推关系来解决它。

首先明确问题：给定正整数$n$，我们要找1到$n$的所有排列$a_1,a_2,\dots,a_n$，满足不等式链：
$$a_1\leq 2a_2 \leq 3a_3 \leq \cdots \leq na_n$$

先算几个小$n$的情况，找感觉 #

• $n=1$：只有排列[1]，显然满足$1\leq1$，答案是1；
• $n=2$：两个排列都满足：
  • [1,2]：$1\leq 2\times2=4$，成立；
  • [2,1]：$2\leq 2\times1=2$，成立；
    答案是2；
• $n=3$：枚举所有6种排列后，筛选出的有效排列为[1,2,3]、[1,3,2]、[2,1,3]，共3个；
• $n=4$：继续枚举后，有效排列有5个。

现在看结果序列：1,2,3,5... 是不是很眼熟？这就是斐波那契数列的前几项！

推导递推关系 #

我们设$f(n)$表示$n$对应的答案，现在分析为什么$f(n)=f(n-1)+f(n-2)$：

1. 情况1：$n$在排列的最后一位（$a_n=n$）
   此时前$n-1$个元素是1~$n-1$的排列，只要满足$a_1\leq2a_2\leq\cdots\leq(n-1)a_{n-1}$即可，这样的排列数就是$f(n-1)$；
2. 情况2：$n$在排列的倒数第二位（$a_{n-1}=n$）
   首先要满足$(n-1)\times n \leq n\times a_n$，两边除以$n$得$n-1\leq a_n$，但$a_n$只能是1~$n-1$中的数，所以$a_n$必须是$n-1$。
   此时前$n-2$个元素是1~$n-2$的排列，满足对应的不等式条件，排列数就是$f(n-2)$；
3. 为什么$n$不能在更靠前的位置？
   假设$n$在第$k$位（$k\leq n-2$），那么$k\times n$是序列中的某一项，后面的第$k+1$位最大能取到$n-1$，$(k+1)(n-1)=kn + (n-k-1)$，虽然它大于等于$k\times n$，但再往后到最后一位，$n\times a_n$的$a_n$只能是剩下的较小数（比如1），此时$n\times1=n$，而$k\times n\geq 2n>n$，必然不满足$k\times n \leq n\times a_n$，所以这种情况没有有效排列。

结论 #

结合初始条件$f(1)=1$，$f(2)=2$，我们可以得到：

• $f(n)$遵循斐波那契数列的递推规律：$f(n)=f(n-1)+f(n-2)$
• 如果把斐波那契数列定义为$F(1)=1,F(2)=1,F(3)=2,F(4)=3,F(5)=5,\dots$，那么$f(n)=F(n+1)$

举个例子验证：

• $f(3)=F(4)=3$，符合；
• $f(4)=F(5)=5$，符合；
• $f(5)=F(6)=8$，验证后确实成立。

备注：内容来源于stack exchange，提问作者CrazedCOmp