每日一题[397]友数列

对给定的正整数$n$，若存在若干个正整数$a_1,a_2,\cdots,a_k$，满足 $$a_1+a_2+\cdots+a_k=n(k=1,2,\cdots),$$ 且$a_1\leqslant a_2\leqslant \cdots \leqslant a_k$，则称数列$a_1,a_2,\cdots,a_k$为正整数$n$的一个“友数列”．若$n$的所有友数列的个数记为$M_n$，对任意一个友数列$\sigma _i^n(i=1,2,\cdots,M_n)$，$A\left(\sigma _i^n \right )$表示数列中数字$1$出现的个数，$B\left(\sigma _i^n \right )$表示数列中出现的不同数字的个数，则研究下列问题：

（1）当$n=4$时，分别写出$M_4,\sum \limits _{i=1}^{M_4} {A\left(\sigma _i^4 \right )},\sum \limits _{i=1}^{M_4} {B\left(\sigma _i^4 \right )}$；

（2）计算$\sum \limits _{i=1}^{M_5} {A\left(\sigma _i^5 \right )}$，并比较其与$M_4+M_3+M_2+M_1+1$的大小；

（3）对给定的正整数$n$，试比较$\sum \limits _{i=1}^{M_n} {A\left(\sigma _i^n \right )}$与$\sum \limits _{i=1}^{M_n} {B\left(\sigma _i^n \right )}$的大小，并说明理由．

解    （1）$M_4=5,\sum \limits _{i=1}^{M_4} {A\left(\sigma _i^4 \right )}=7,\sum \limits _{i=1}^{M_4} {B\left(\sigma _i^4 \right )}=7$.

（2）因为$\sum \limits _{i=1}^{M_5} {A\left(\sigma _i^5 \right )}=12$，及 $$M_4+M_3+M_2+M_1+1=5+3+2+1+1=12,$$ 所以 $$\sum \limits _{i=1}^{M_5} {A\left(\sigma _i^5 \right )}=M_4+M_3+M_2+M_1+1.$$

（3）对给定的正整数$n$，一方面，在所有$M_n$个友数列中，首项为$1$的有$M_{n-1}$个，第二项为$1$的有$M_{n-2}$个，$\cdots$，第$n-1$项为$1$的有$M_1=1$个，第$n$项为$1$的有$1$个，因此 $$\sum \limits _{i=1}^{M_n} {A\left(\sigma _i^n \right )} =M_{n-1}+M_{n-2}+\cdots+M_2+M_1+1.$$
另一方面，在所有$M_n$个友数列中，从含有$1$的一个友数列里去掉一个$1$，则成为$n-1$的一个友数列，共有$M_{n-1}$个，即出现$1$的数列有$M_{n-1}$个；从含有$2$的一个友数列里去掉一个$2$，则成为$n-2$的一个友数列，共有$M_{n-2}$个，即出现$2$的数列有$M_{n-2}$个；$\cdots$；从含有$n-1$的一个友数列里去掉一个$n-1$，则成为$1$的一个友数列，共有$M_{1}$个；最后加上含有$n$的$1$个友数列．因此 $$\sum \limits _{i=1}^{M_n} {B\left(\sigma _i^n \right )} =M_{n-1}+M_{n-2}+\cdots+M_2+M_1+1.$$

综上所述，$\sum \limits _{i=1}^{M_n} {A\left(\sigma _i^n \right )}=\sum \limits _{i=1}^{M_n} {B\left(\sigma _i^n \right )}$．

注　$\sum \limits _{i=1}^{M_n} {B\left(\sigma _i^n \right )}$的计算中用到了“算两次”的思想，即对$n$的每个友数列分别统计其中出现的不同数字的个数（即左边），再将所有的友数列合在一起，计算$1,2,\cdots,n$在这些数列中出现的次数（在同一个友数列中，多次算成一次）再相加（即右边），两者结果相同得到结论，更多相关问题见每日一题[356]算两次．