|
关于白新岭[原创]限定定义域方程的正整数解 的个人理解
想解决上述问题,首先需要解决不定方程的正整数解的组数问题。线性不定方程x+y+z+.....+u=n,这里的未知数及n都是正整数。现在我们求它的正整数解的组数。这个问题很容易解决,我们可以把n个数看成n个物体,把这n个物体排成一排,用m-1块木板(m为未知数的个数)把这一排物体分成m段,则划分段的方法数既是不定方程的正整数解的组数,根据计数原理,可知m-1块木板把n个物体分成C(n-1,m-1). (物体与物体之间有n-1个空隙可以放木板)
(X-1)+(Y-1)+(Z-1)+....+(U-1)=n的正整数解的组数与x+y+z+.....+u=n的非负正整数解的组数相同(这里设x=X-1,y=Y-1,z=Z-1,....u=U-1),前边的不定方程的正整数解的组数为C(n+m-1,m-1),所以,后边线性不定方程x+y+z+.....+u=n的非负正整数解的组数为C(n+m-1,m-1).
这是49楼的内容。现在我们用公式求一下x+y+z=100的非负整数解的组数,有公式可知为C(100+3-1,3-1)=C(102,2)=102*101/2=5151组非负整数解。x=0,y+z=100有101组非负整数解;x=1,(y+z=99)有100组非负整数解;......;x=100,有1组非负整数解;这样x从0取到100已经遍历所有情况,所以1+2+3+...+99+100+101=(1+101)*101/2=5151组非负整数解。
现在我们看一看x+y+z=3001在x,y,z没有因子3,4,5的情况下有多少组符合条件的正整数解。模3的非0余数有1,2;即如果把自然数分成3类,可以分成3n+1,3n+2,3n三种类型;按模4可以把自然数分成4种类型,4n+1,4n+2,4n+3,4n;按模5可以把自然数分成5种类型,5n+1,5n+2,5n+3,5n+4,5n。如果想把这些余数情况综合起来考虑,就需要3*4*5=60种类型,这样符合条件的类型有(3-1)*(4-1)*(5-1)=2*3*4=24种,它们分别为60n+1,60n+2,60n+7,60n+11,60n+13,60n+14,60n+17,60n+19,60n+22,60n+23,60n+26,60n+29,60n+31,60n+34,60n+37,60n+38,60n+41,60n+43,60n+46,60n+47,60n+49,60n+53,60n+58,60n+59。在这24种类型数中无论用那3个数,都不会含有因子3,4,5,又因为有3个位置(3个未知数)每个位置有24种不同类型可选,所以有24*24*24=13824种合成方法,每种类型都含有加子60n,它们的和对公共模3*4*5=60来说,不影响结果对模60的余数,(即参与运算与不参与运算不会影响余数(小于等于59)),所以我们把相同的加法算子去掉(把60n去掉),只对1,2,7,11,13,14,17,19,22,23,26,29,31,34,37,38,41,43,46,47,49,53,58,59这24种余数算子做3维加法合成(这里的运算与常规的加法运算不同,与群中元素的2元乘法运算也不同),用excel软件可以得到24种余数3维合成结果的分布情况。
1周→方法数→2周→方法数→3周→方法数
1→→0→→61→150→→121→123
2→→0→→62→162→→122→111
3→→1→→63→93→→123→88
4→→3→→64→123→→124→108
5→→3→→65→138→→125→111
6→→1→→66→109→→126→72
7→→0→→67→180→→127→93
8→→0→→68→141→→128→93
9→→3→→69→109→→129→70
10→→6→→70→150→→130→96
11→→3→→71→183→→131→87
12→→0→→72→114→→132→42
13→→3→→73→186→→133→84
14→→6→→74→192→→134→75
15→→9→→75→108→→135→51
16→→12→→76→159→→136→63
17→→9→→77→201→→137→63
18→→3→→78→133→→138→46
19→→9→→79→204→→139→60
20→→12→→80→156→→140→48
21→→13→→81→132→→141→37
22→→18→→82→204→→142→51
23→→12→→83→207→→143→54
24→→6→→84→126→→144→24
25→→24→→85→186→→145→42
26→→27→→86→210→→146→36
27→→21→→87→136→→147→25
28→→21→→88→177→→148→36
29→→24→→89→213→→149→36
30→→18→→90→132→→150→18
31→→36→→91→213→→151→24
32→→36→→92→177→→152→21
33→→25→→93→136→→153→21
34→→36→→94→210→→154→27
35→→42→→95→186→→155→24
36→→24→→96→126→→156→6
37→→54→→97→207→→157→12
38→→51→→98→204→→158→18
39→→37→→99→132→→159→13
40→→48→→100→156→→160→12
41→→60→→101→204→→161→9
42→→46→→102→133→→162→3
43→→63→→103→201→→163→9
44→→63→→104→159→→164→12
45→→51→→105→108→→165→9
46→→75→→106→192→→166→6
47→→84→→107→186→→167→3
48→→42→→108→114→→168→0
49→→87→→109→183→→169→3
50→→96→→110→150→→170→6
51→→70→→111→109→→171→3
52→→93→→112→141→→172→0
53→→93→→113→180→→173→0
54→→72→→114→109→→174→1
55→→111→→115→138→→175→3
56→→108→→116→123→→176→3
57→→88→→117→93→→177→1
58→→111→→118→162→→178→0
59→→123→→119→150→→179→0
60→→72→→120→72→→180→0
上边的数据是24种余数相加结果不同的分布情况,一周表示3种余数相加的值不超过60的。例如在一周所在列的59就是3种余数和为59的,第二列是分列符号,第三列是第一列对应的合成放法数,59对应123,就是说有123种余数加法的和为59.后边的列数据含义与这里的解释相同。第五列的2周和结果与第七列的合成方法相对应;第九列的3周和结果与第十一列的合成方法相对应。
根据计数原理,我们就得到求解组数公式,例如MOD(3001,60)=1,即3001对应照余数为1的情况,3001/60=50余1,也就是50个60整体可以分别放在x,y,z上,在1周上有0种合成方法,所以本类合成方法数为0;拿出1个60,和余数1加在一起,则其和为61,余数相加得到61的方法数为150种,而C(60-1+3-1,3-1)=C(59+3-1,3-1)=C(61,2)=61*60/2=1830,有150*1830=274500;拿出2个60,和余数1加在一起,则其和为121,余数相加得到121的方法数为123种,而C(60-2+3-1,3-1)=C(58+3-1,3-1)=C(60,2)=60*59/2=1770,有123*1770=217710;三个周期的方法和0*C(60+3-1,3-1)+150*C(60-1+3-1,3-1)+123*C(60-2+3-1,3-1)=0+150*1830+123*1770=492210. |
|