|
细说哥猜中的“哈代_李特伍德公式”
这里是与熊一兵先生的聊天记录:
求不定方程x+y+z+........+u=n(有m个未知数)的正整数解的组数,在组合数学中应该有吧!(我不知道),这个问题很好解决,我们把n个整数1看成n个物体,把这n个物体排列成一排,则n个物体间有n-1个空隙,拿m-1块木板把这n个物体隔开,正好分割成有序的m堆物体,按顺序把x,y,z,.....u与分割好的m堆物相对应,未知数取每堆物体的个数,则每一种分法就是方程的一组正整数解,而木板的方法等于从n-1个空隙上抽m-1个空隙法,即为C(n-1,m-1),所以不定方程x+y+z+........+u=n(有m个未知数)的正整数解的组数为:C(n-1,m-1)=(n-1)!/(m-1)!/(n-m)!.
有了这个结论,就可以得到不定方程x+y+z+........+u=n(有m个未知数)的非负整数解的组数。方程两边各加上m,变为(x+1)+(y+1)+(z+1)+........+(u+1)=n+m,另X=x+1,Y=y+1,Z=z+1,...,U=u+1,则方程变为X+Y+Z+.....+U=n+m,变形后方程的正整数解的组数为:C(n+m-1,m-1),这也就是原方程的非负整数解的组数。
在后边方程解的基础上,我们就可以解决条件方程解的组数了。
例如方程x+y+z=n,x,y,z不能整除6,则x,y,z只能取6t+1,6t+2,6t+3,6t+4,6t+5这5类数,n可以有t的6种函数式表示, 未完待续,我要下班了。
上午举得例子未写完(不知你看了没有)。拿一个具体的数,比较好理解。就设n=604吧。这个n分成两部分,一个为6的整倍数部分是600,除6,等于100,另外一部分是4,因为x,y,z不能整除6,所以把x,y,z也分成两部分,即把x,y,z写成6t+b的形式,这里0<b<6,为整数。先看b组成余数4的情况,至于周期t的分配好算出,是X+Y+Z=100的非负整数解的组数。那么有:1,2,3,4,5这5个元素做3元加法,会得到怎样的分布呢?
独木星空 16:05:21
1 2 3 4 5
1 2 3 4 5 6
2 3 4 5 6 7
3 4 5 6 7 8
4 5 6 7 8 9
5 6 7 8 9 10
第一行和第一列为参与运算的5个元素,其余部分是2元加法运算的结果。
1 2 3 4 5
2→ 3→ 4→ 5→ 6→ 7
3→ 4→ 5→ 6→ 7→ 8
4→ 5→ 6→ 7→ 8→ 9
5→ 6→ 7→ 8→ 9→ 10
6→ 7→ 8→ 9→ 10→ 11
3→ 4→ 5→ 6→ 7→ 8
4→ 5→ 6→ 7→ 8→ 9
5→ 6→ 7→ 8→ 9→ 10
6→ 7→ 8→ 9→ 10→ 11
7→ 8→ 9→ 10→ 11→ 12
4→ 5→ 6→ 7→ 8→ 9
5→ 6→ 7→ 8→ 9→ 10
6→ 7→ 8→ 9→ 10→ 11
7→ 8→ 9→ 10→ 11→ 12
8→ 9→ 10→ 11→ 12→ 13
5→ 6→ 7→ 8→ 9→ 10
6→ 7→ 8→ 9→ 10→ 11
7→ 8→ 9→ 10→ 11→ 12
8→ 9→ 10→ 11→ 12→ 13
9→ 10→ 11→ 12→ 13→ 14
6→ 7→ 8→ 9→ 10→ 11
7→ 8→ 9→ 10→ 11→ 12
8→ 9→ 10→ 11→ 12→ 13
9→ 10→ 11→ 12→ 13→ 14
10→ 11→ 12→ 13→ 14→ 15
有第一行的一元的5个元素与第一列的25个2元加法结果再相加,得到最终结果:
3元结果→ 出现次数
3→ 1
4→ 3
5→ 6
6→ 10
7→ 15
8→ 18
9→ 19
10→ 18
11→ 15
12→ 10
13→ 6
14→ 3
15→ 1
余数4在第一周期出现了3次,即余数1,1,2的全排列;在第二周期它(10=6+4)出现了18次,即余数1,4,5的全排列,余数2,3,5的全排列,余数2,4,4的全排列,余数3,3,4的全排列;第三周期未出现。
所以当n=604时,方程的正整数解的组数为:3*C(100+3-1,3-1)+18*C(100-1+3-1,3-1)+0*C(100-2+3-1,3-1)=3*102*101/2+18*101*100/2+0=106353.
解决问题思路,把n分成两部分,一部分是条件的整倍数,一部分是余数,整倍数的取得是减1后向下取整,即为[(n-1)/6],中括号为取整函数。不知道大家能否理解。有兴趣的可以求一下x+y+z=n,这里的未知数不能整除3,4.(给的条件要互质),它有12种情况,即n=12t+1,12t+2,12t+3,12t+4,12t+5,12t+6,12t+7,12t+8,12t+9,12t+10,12t+11,12t+12.(t从0到无穷大),谁能给出关于t的2次函数公式表达式。
在解决歌猜前,还是先把不定方程在限制条件下方程解的组数问题搞清楚,弄明白为好,这样会对歌猜有深刻的认识,水到渠成,磨刀不误砍柴工。 |
|