积的和』形式。

嗯？

「积的和」……吗？

而且是C<k>和C<n－k>这种「标记之和为n」的形式……吗？

原来如此。

我想起自己对蒂蒂说过的话了。

……不要将n－k和k分开思考，而是要想『和就是n』，然后在这个和中从0到n间取平衡……

这次的递推公式也很类似，C<k>和C<n－k>的标记之和为n，然后为了和的平衡，k会在0与n之间变动。

现在知道的递推公式C<n＋1>＝Σ<k=0到n,C<k>C<n－k>>是这样表现的，假如能好好运用Σ<k=0到n,C<k>C<n－k>>作成「积的和」的形式，就可以用这样比较单纯的项置换。

仔细想想，有哪些场合会出现「积的和」。

……将这种「和的积」变成x<立方>＋3x<平方>y＋3xy<平方>＋y<立方>这种「积的和」，这就是展开……

将「和的积」展开，就会变成「积的和」吗？

好。

关键似乎就是积了，试试看生成函数的积吧，动手算或许就能发现什么。

由于只有生成函数C，所以先试试看平方会出现什么呢？生成函数如下。

C＝C<0>＋C<1>x＋C<2>x<平方>＋……＋C<n>x<n次方>＋……

所以平方的话……会变成这样。

C<平方>＝＋x＋x<平方>＋……

常数项是C<0>C<0>，x项系数是C<0>C<1>＋C<1>C<0>，x<平方>项系数是C<0>C<2>＋C<1>C<1>＋C<2>C<0>啊。

接着用广义化——我想起了蒂蒂那双大眼睛——表现C<平方>的x<n次方>系数

宁静的空间中只剩下写字的沙沙声。

……完成了，这就是x<n次方>的系数。

C<0>C<n>＋C<1>C<n－1>＋……＋C<k>C<n－k>＋……＋C<n－1>C<1>＋C<n>C<0>

要注意标记的部分，而在C<k>C<n－k>中，左边的k渐渐变大，右边的n－k渐渐变小，k在0到n的范围内移动。

到这里为止写得相当冗长不容易懂，所以使用Σ，广义来说，x的系数就是

Σ<k=0到n,C<k>C<n－k>>

由于这是C<平方>这个式子的「x<n次方>的系数」，所以C<平方>这个式子就会变成二重和的形式……写成……

C<平方>＝Σ<n=0到∞,Σ<k=0到n,C<k>C<n－k>>x<n次方>>

出来了。

求出来了！

求出漂亮的「积的和」Σ<k=0到n,C<k>C<n－k>>了，所以之后这个部分应该可以用递推公式简化，由递推公式得……

Σ<k=0到n,C<k>C<n－k>>

可以置换成以下这个单纯的项。

C<n＋1>

也就是说……

可以将生成函数C的平方大幅简化了，将C<k>C<n－k>用C<n＋1>替换吧。

C<平方>＝C<平方>＝Σ<n=0到∞,Σ<k=0到n,C<k>C<n－k>>x<n次方>>

＝C<平方>＝Σ<n=0到∞,C<n＋1>x<n次方>>

喔～～二重和变成一般的和了。

不过等一下，C<n＋1>的标记和x<n次方>的指数差了1。

嗯～～啊，对了，消除差距的状况在斐波那契数列的时候也有过，只要将差距的部分乘上x就好，将两边乘x…