就是我的学妹，她会像小松鼠或是小狗、小猫一样地黏着我，常常跑来问我一些数学的问题，不只是针对不懂的问题，也会提出根本上的疑问，虽然有点黏人，不过也不算是困扰。

「很急吗？」

「不、不会不会，没关系，只是有点事想问而已。」蒂蒂边向我摇手边后退三步。「打扰到你就不好了，所以等你要回去的时候再……今天也会待到关门吗？」

「是啊，我想应该会待到瑞谷管理员来宣布闭校为止，要一起回去吗？」

我偷偷地看向窗边，米尔迦面对桌子坐着，并将注意力集中在纸上，由于她背对着我，所以看不到她的表情，而她也没有任何动作。

「好的，请务必让我陪同，那我先告辞了。」

蒂蒂轻巧地踏稳脚步，在敬礼之后向右转，直接走出图书室，不过她在出去的那一瞬间偷偷瞄了米尔迦一眼。

7．1．3递推公式

那么，回到「括括号方法的总数」的递推公式。

从0到4有5个数，中间有4个加号。仔细想想，现在要求的是「括括号方法的总数」，所以那些数字本身并没有意义。也就是说：

＋))

可以用下列算式取代。

＋))

为了要做出递推公式，就必须看穿『括括号方法』背后的构造，然后找出规则性。由于这个式子有四个加号，所以先汇整成3个加号以下的状况，也就是说……

＋))——加号有四个

这种模式，也可以用这种情况来看。

＋))

1个加号2个加号

嗯，看出来了，最后的加号——也就是要注意最后才会加到的加号在哪里，以上式为例，从左边数来第二个是最后的加号，整个式子会根据最后的加号分成左右两个式子，将加号的位置从左边开始顺序移动的话，就能做出排他性质的类别，有4个加号的式子可以区分成以下4种，如果在最后的加号做上<>，会像下面一样。

<+>)

<+>)

<+>)

<+>)

在这个分类里，还是有像一样还没括完括号、依然是3项以上的和，不过加号的个数越变越少，所以可以带入之前的形式，嗯，这样似乎就能做出递推公式了。

有四个加号的形式，也就是说：

有以下类别。

<分别对应于>

<分别对应于>

<分别对应于>

<分别对应于>

从这里开始发展成「类别的个数」。将「有n个加号的式子的括括号方法的总数」以C<n>表示的话，就能做出对C<n>的递推公式。

「分别对应于」的意思就是对应到「方法的总数」的积，在n＝4的状况，也就是以C1来表现式子时，C4会是下面4项的和。

C<0>×C<3>，C<1>×C<2>，C<2>×C<1>，C<3>×C<0>

也就是C<4>能写成下面式子。

C4＝C<0>C<3>＋C<1>C<2>＋C<2>C<1>＋C<3>C<0>

不错，这样就能广义化了。

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

出现了漂亮的式子了，在这里使用Σ让结构能更清楚呈现。

C<0>＝1

C<n＋1>＝Σ<k=0到n,C<k>C<n－k>>

很好，这样递推公式就完成了。

赶快来验算吧。

C<0>＝1

C<1>＝Σ<k=0到0,C<k>C<0－k>>＝C<0>C<0>＝1

C<2>＝Σ<k=0到1,C<k>C<1－k>>＝C<0>C<1>＋C<1>C<0>＝2

C<3>＝Σ<k=0到2,C<k>C<2－k>>＝C<0>C<2>＋C<1>C<1>＋C<2>