n=n1+n2+…+nm(n1≥n2≥…≥nm≥1)的一种表示法,叫做n的一种分拆.对被加项及项数m加以一些限制条件,就得到某种特殊类型的分拆.早在中世纪,就有关于特殊的整数分拆问题的研究.1742年德国的哥德巴赫提出“每个不小于6的偶数都可以写成两个奇质数的和”,这就是著名的哥德巴赫猜想.
一、整数分拆中的计数问题
例1 有多少种方法可以把6表示为若干个自然数之和?
解:根据分拆的项数分别讨论如下:
①把6分拆成一个自然数之和只有1种方式;
②把6分拆成两个自然数之和有3种方式
6=5+1=4+2=3+3;
③把6分拆成3个自然数之和有3种方式
6=4+1+1=3+2+1=2+2+2;
④把6分拆成4个自然数之和有2种方式
6=3+1+1+1=2+2+1+1;
⑤把6分拆成5个自然数之和只有1种方式
6=2+1+1+1+1;
⑥把6分拆成6个自然数之和只有1种方式
6=1+1+1+1+1+1.因此,把6分拆成若干个自然数之和共有
1+3+3+2+1+1=11种不同的方法.
说明:本例是不加限制条件的分拆,称为无限制分拆,它是一类重要的分拆.
例2 有多少种方法可以把1994表示为两个自然数之和?
解法1:采用有限穷举法并考虑到加法交换律:
1994=1993+1=1+1993
=1992+2=2+1992
=…
=998+996=996+998
=997+997
因此,一共有997种方法可以把1994写成两个自然数之和.
解法2:构造加法算式:
1994=1+1+1+1+.........+1(1994个1相加)
于是,只须考虑从上式右边的1993个加号“+”中每次确定一个,并把其前、后的1分别相加,就可以得到一种分拆方法;再考虑到加法交换律,因此共有997种不同的分拆方式.
说明:应用本例的解法,可以得到一般性结论:把自然数n≥2表示为两个自然数之和,一共有k种不同的方式,其中
(1)K=N/2 (N是偶数)
(2) K=(N-1)/2 (N是奇数)
例3 有多少种方法可以把100表示为(有顺序的)3个自然数之和?(例如,把3+5+92与5+3+92看作为100的不同的表示法)
分析 本题仍可运用例1的解法2中的处理办法.
解:构造加法算式
100=1+1+1+1+.......+1 (100个1相加)
于是,考虑从上式右边的99个加号“+”中每次选定两个,并把它们所隔开的前、中、后三段的1分别相加,就可以得到一种分拆方法.因此,把100表示为3个自然数之和有C(99,2)=99*98/2=4851 种不同的方式.
说明:本例可以推广为一般性结论:“把自然数n≥3表示为有顺序的3个自然数之和,共有(N-1)(N-2)/2种不同的方式
练习题:
1. 有多少种方法可以把10表示为若干个自然数之和?
2.有多少种方法可以把3335表示为两个自然数之和?
3. 有多少种方法可以把1000表示为(有顺序的)4个自然数之和?
4.用1分、2分和5分的硬币凑成一元钱,共有多少种不同的凑法?