再问一个数列题

hongxian

有$n$($n\geqslant2,n\in N^*$)个小球，将它们任意分成两堆，求出这两堆小球球数的乘积，再将其中一堆小球任意分成两堆，求出这两堆小球球数的乘积，如此下去，每次都任选一堆，将这堆小球任意分成两堆，求出这两堆小球球数的乘积，直到不能再分为止，则所有乘积的和为_____________；

kuing

似乎跟分法有关吧，比如说4个球

4=1+3
=1+1+2
=1+1+1+1
S=3+2+1

4=2+2
=2+1+1
S=4+1

难道我理解错题意了？

hongxian

回复 2# kuing

例如，对于4粒球有如下两种分解：（4）$\rightarrow$（1，3）$\rightarrow$（1，1，2）$\rightarrow$（1，1，1，1），此时$S_4=1×3+1×2+1×1=6$；（4）$\rightarrow$（2，2）$\rightarrow$（1，1，2）$\rightarrow$（1，1，1，1），此时$S_4=2×2+1×1+1×1=6$，于是发现$S_4$为定值6

kuing

回复 3# hongxian

题目不是说每次在分出来的两堆中任选一堆再分吗？没选的就不管了吧？

hongxian

回复 4# kuing

例子是题中的例子，我太懒先没有打出来，最后都要分成1个一堆

hongxian

特例法得到结果$\dfrac{n(n-1)}{2}$不难，只是为什么是定值，不知有没有人有兴趣考虑一下？
好象可以数归

kuing

回复 6# hongxian

嗯，数归可以，不过是第二数归。

下面证明：当有 $n$ 个球时，无论如何分，最终所有乘积之和都为 $f(n)=n(n-1)/2$。

当 $n=2$ 时显然 $f(2)=1$；
假设当 $2\leqslant n\leqslant k$ 时恒有 $f(n)=n(n-1)/2$，则当 $n=k+1$ 时，设第一步分成的两堆的个数分别为 $p$ 和 $k+1-p$，若 $p=1$，则\[f(k+1)=k+f(k)=k+\frac{k(k-1)}2=\frac{k(k+1)}2,\]
同理当 $p=k$ 时亦有 $f(k+1)=k+f(k)=k(k+1)/2$，而当 $2\leqslant p\leqslant k-1$ 时，因为 $p$, $k+1-p\in[2,k]$，由归纳假设可知
\[f(k+1)=p(k+1-p)+f(p)+f(k+1-p) =p(k+1-p)+\frac{p(p-1)}2+\frac{(k+1-p)(k-p)}2 =\frac{k(k+1)}2,\]
可见总有 $f(k+1)=k(k+1)/2$。

综上，由第二数归知结论得证。

hongxian

回复 7# kuing

K考虑问题就是全面，$n=1$我没有分开讨论，我想$f(1)=0$好象也说得过去，却没有注意到题目中有一个$n \geqslant 2$

kuing

搜索题目出处时无意中搜到这个贴
zhidao.baidu.com/question/568091650.html
这个贴的构造性解法太妙了

kuing

按照这贴 jyeoo.com/math2/ques/detail/c1f51bb7-ae08-4ac4-a744-22b6bc67a386 的标示，题目出处是2010•南通模拟

hongxian

回复 9# kuing


    实在是妙！

其妙

回复 10# kuing
特殊值法探路，

青青子衿

10．个乒乓球,将它们任意分成两堆,求出这两堆乒乓球个数的乘积,再将每堆乒乓球任意分成两堆并求出这两堆乒乓球个数的乘积,如此下去,直到不能再分为止,则所有乘积的和为________
佛山市2015届普通高中高三教学质量检测(一)(文数)
2015年福建省漳州市高三5月适应性考试文科数学

活着＆存在

把问题反过来看，就是先有N堆球，每堆一个；然后任意选两堆合并，直到不能合并（即最后合成一堆）。这样跟N个元素中任意取两个有关系。例如：ABCD依次四个球。
（1，1，1，1）——（1，2，1）——（2，2）——（4）表示先取BC，再取AD，最后是AD中选一个跟BC中选一个去结合，1+1+4=6。把所有乘积加起来，就是把所有可能的种数算出来。——就是一个组合数。
例如：ABCDE依次5个球。
（1，1，1，1，1）——（1，1，2，1）——（1，1，3）——（2，3）——（5）表示CD组合，然后CD中选一个跟E组合，然后AB组合，最后AB中选一个和CDE中选一个组合。把所有乘积相加，就表示5选2的组合有几个。

青青子衿

好像不相关……
整数分拆中的一个出人意料的结论
matrix67.com/blog/archives/6348

其妙

变式题：
数列$\{2^n-1\}$的前$n$项组成集合$A_n=\{1，3，7，…，2^n-1\}（n∈N_*）$，从集合$A_n$中任取$k（k=1，2，3，…，n）$个数，其所有可能的$k$个数的乘积的和为$T_k$（若只取一个数，规定乘积为此数本身），记$S_n=T_1+T_2+…+T_n$．例如：当$n=1$时，$A_1=\{1\}$，$T_1=1，S_1=1$；当$n=2$时，$A_2=\{1，3\}，T_1=1+3，T_2=1×3，S_2=1+3+1×3=7$．求$S_n$