每日一题[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 )}$的大小,并说明理由.


cover

解    (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]算两次

此条目发表在每日一题分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论