一直没有说话的米尔迦用手拍了桌子,她想仿真爆发的音效吗?
我们愕然地停下对话。
「蒂德菈到那个角落,你去窗边的位置,而我在这里,大家都不要小说话、安静地思考。」
米尔迦一声令下,蒂蒂和我都点头同意。
「知道了还不快点行动。」
……我们就在放学后的图书室里在无声地开始用功。
10.1.2思考实例
面额依正整数(1,2,3,4,……)变化的硬币,用这些硬币来支付n元,这是求支付的方法数——分拆数——的问题。
和从前一样,我先从小的数进行具体的思考,用实例来抓到感觉是很重要的。
当n=0的时候,也就是支付金额为0的状况……只有「不支付」一种方法,方法数为1,也可以说P<0>=1。
P<0>=1支付0元的方法有1种
当n=1的时候……只有「使用1个1元」一种方法,所以P<1>=1。
P<1>=1支付1元的方法有1种
当n=2的时候……有「使用1个2元」与「使用2个1元」的方法,所以P<2>=2。
P<2>=2支付2元的方法有2种
当n=3的时候……有「使用1个3元」与「使用1个2元、1个1元」与「使用3个1元」3种方法。
由于再这样写下去太麻烦,所以「使用1个2元、1个1元」这种方法,就用2+1表现,也就是这种写法。
2+1(2元用1枚,1元用一枚)
当n=3时有以下的3种方法。
3=3
=2+1
=1+1+1
等同于P<3>=3。
P<3>=3支付3元的方法有3种
唔,所谓的P<3>虽然是「支付3元的方法数」,不过也可以说成「将3分拆成数个正整数的方法数」,所以才被命名为「分拆数」吧。
n=4的话,如下有5种,一共5个分拆,嗯,我已经抓到诀窍了
4=4
=3+1
=2+2
=2+1+1
=1+1+1+1
P<4>=5支付4元的方法有5种
n=5的话……有以下7种。
5=5
=4+1
=3+2
=3+1+1
=2+2+1
=2+1+1+1
=1+1+1+1+1
P<5>=7支付5元的方法有7种
像这样让n逐渐变大时,就能稍微发现一些规则,数字倘若不够大,要找出规则性就不容易,以前米尔迦说过「少量的样本不容易发现规则」,但是数字增加得太大,具体举例就会变得困难。
继续下去吧,令n=6,有以下11种表现方法。
6=6
=5+1
=4+2
=4+1+1
=3+3
=3+2+1
=3+1+1+1
=2+2+2
=2+2+1+1
=2+1+1+1+1
=1+1+1+1+1+1
P<6>=11支付6元的方法有11种
嗯,P<2>,P<3>,P<4>,P<5>,P<6>=2,3,5,7,11,是和质数有关的规律吗?
P<7>会是13吗?
7=7
=6+1
=5+2
=5+1+1
=4+3
=4+2+1
=4+1+1+1
=3+3+1
&em