[原创]用高中的排列组合知识解不定方程的正整数解的组数

白新岭

[这个贴子最后由白新岭在 2009/03/25 02:24pm 第 3 次编辑]

[watermark]我们用高中的排列组合知识解方程x+2y+3z=N的正整数解的组数数目。分两种情况，一种是N能被3整除，一种是不能被3整除。
（一），当N不能被3整除时，方程x+2y+3z=N可以写成(x+y+z)+(y+z)+z=N,所有原方程的一组解都可以与一组无序的数一一对应，例如x=x1,y=y1,z=z1时与(x1+y1+z1)，(y1+z1)，z1对应，而且对应的一组数中的3个数都不相等。所以对应的每组做全排列的话，都有3！=6排列方法。接着我们分析这样的分段，把从第1位到N位的N个1分成3段，则有C(N-1,2）=（N-1)*(N-2)/2种分法（解释，N个1相接，1与1之间有N-1个空，从这N-1个空中任选2个空放2块木板可以把N个1分成3段，因为不能整除3，所以不能分出3段都一样的1的个数），这样的分段会出现那几种情况，一种情况，分出的段含1的个数都不同；另一种情况，其中2段的数字相同。设分成的三段含1的个数都不同的方法为s种，则s一定是6的倍数，因为当三段不同时，有3！种排列顺序。2段相同，另一段不同，这样方法有m种，则m一定是3的倍数，因为当有二段相同时，有3种排列顺序。分成3段总排列顺序为C(N-1,2)=(N-1)*(N-2)/2=s+m,
s除6即为方程的正整数解的组数数目，现在需求m的值，2段相同，另一段不同，可得x+2y=N,这里x与y一定不同，如果相同，则x=y,方程x+2y=N变为3y=N，无解（N不能整除3），方程x+2y=N解的个数有[(N-1)/2]个解，从N物体中2个2个的拿的方法有，拿2，4，6，...，2k,N是2的倍数时，最后1组2不能拿，N是奇数时，只能有(N-1)/2种拿法，所以无论N是奇数，还是偶数，方程一定是[(N-1)/2]个解。另外我们已知道3个数，如果2个相同，1个不同的排列数是3，所以m=3*[(N-1)/2]，s+m=(N-1)*(N-2)/2,推出:
S/6=((N-1)*(N-2)/2-3*[(N-1)/2])/6.这里的中括号是取整函数。
（二）当N能被3整除时，总方法中有1种排列是3段都一样的，另外在2段一样中也去掉一种，所以S/6=((N-1)*(N-2)/2-3*[(N-1)/2]+2)/6.这里的中括号是取整函数。
举2个例子，x+2y+3z=2009或2010.
当等于2009时，不能整除3，属于第一种情况：S/6=((2009-1)*(2009-2)/2-3*[(2009-1)/2])/6=335336.
当等于2010时，能整除3，属于第二种情况：
S/6=((2010-1)*(2010-2)/2-3*[(2010-1)/2]+2)/6=335671.
主要思路是把一排物体分成3段，分得3段出现几种情况的排列。3段都不同时出现3！排列顺序；有2段相同时有3种排列顺序；3段都一样时只有1种排列顺序。再有当有2段相同时，有几种组合，可以求从N个物体中2个2个的拿，至少剩一个物体的拿法数。在就是转换问题，通过一一映射关系，保证不改变数目。

[/watermark]

白新岭

此问题的关键是把方程的正整数解的数目一一对应到一种组合上去，每种相同构造的组合有多少种排列顺序。原问题是从k个自然数数和的分布问题引出。当未知数增多时，系数不连续时，问题会变的复杂。不过，用Excel软件，通过简单公式设计即可得到不是很多未知数方程的正整数解的组数数目（不超过250个未知数吧）

白新岭

[这个贴子最后由白新岭在 2009/03/25 03:01pm 第 2 次编辑]

用4个不同的自然数，其和为2009的组合有多少？（或者把2009拆分成4个不同的正整数有多少种方法）
luyuanhong教授给出2009的整数分拆数目(拆分成4个正整数）,也给出了把一个整数拆分2个，3个，或4个自然数的分拆数目公式。（没有给出用4个不同的自然数使其和为2009的组合数目，不过以前证明过:x+2y+3z+....+mu=N(1,2,3,...,m为系数，x,y,z,..,u为未知数，正好m个未知数）m元线性方程正整数解的组数与把N拆成m个整数的数目之间的关系，只需要把拆成m个整数中的N减去m*(m-1)/2即可，假设我们用S(N,m)表示方程x+2y+3z+....+mu=N的正整数解的组数，用D(N,k)表示整数N拆分成k个整数的数目，则它们之间有这样的关系：
S(N,m)=D(N-m*(m-1)/2,m)或者D(N,k)=S(N+k*(k-1)/2,k).

luyuanhong

下面是我求得的一些结果：

白新岭

luyuanhong教授给出了4以前整数拆分公式，非常感谢.
一下是我计算给出的正整数解的组数公式：
我们用S(n,m)表示线性多元方程x+2y+3z+....+mu=n的正整数解的组数（这里1，2，3，...，m为已知系数，x,y,z,...,u为未知数，正好m元，n是预先给定的一个正整数。
（一）当m=2时，S(n,2)=[(n-1)/2]. 这里中括号为取整函数。
（二）当m=3时，S(n,3)有2*3=6个公式：
     （1）当n=6k-5时，S(n,3)=3*k^2-8*k+5
     （2）当n=6k-4时，S(n,3)=3*k^2-7*k+4
     （3）当n=6k-3时，S(n,3)=3*k^2-6*k+3
     （4）当n=6k-2时，S(n,3)=3*k^2-5*k+2
     （5）当n=6k-1时，S(n,3)=3*k^2-4*k+1
     （6）当n=6k  时，S(n,3)=3*k^2-3*k+1
（三）当m=4时，S(n,4)有2*3*2=12个公式：（公式个数为系数的最小公倍数）
     （1）当n=12k-11时，S(n,4)=12k^3-48*k^2+63*k-27
     （2）当n=12k-10时，S(n,4)=12k^3-45*k^2+56*k-23
     （3）当n=12k- 9时，S(n,4)=12k^3-42*k^2+48*k-18
     （4）当n=12k- 8时，S(n,4)=12k^3-39*k^2+42*k-15
     （5）当n=12k- 7时，S(n,4)=12k^3-36*k^2+35*k-11
     （6）当n=12k- 6时，S(n,4)=12k^3-33*k^2+30*k-9
     （7）当n=12k- 5时，S(n,4)=12k^3-30*k^2+24*k-6
     （8）当n=12k- 4时，S(n,4)=12k^3-27*k^2+20*k-5
     （9）当n=12k- 3时，S(n,4)=12k^3-24*k^2+15*k-3
    （10）当n=12k- 2时，S(n,4)=12k^3-21*k^2+12*k-2
    （11）当n=12k- 1时，S(n,4)=12k^3-18*k^2+ 8*k-1
    （12）当n=12k   时，S(n,4)=12k^3-15*k^2+ 6*k-1
当然对于S(n,4)公式中的系数（不包括最高项）是可以缩小的（绝对值），2次项系数可以从-21，-18，-15，.....，0，3，6，9，12.
1次项可以从12，8，6，3，2，0，0，-1，0，0，2，3.
常数项可以为-2，-1，-1，0，0，0，0，0，0，0，0，0.
这样写出来的公式简化运算量。
至于m=5,6,7,...,公式都可以写出来，而且公式有规律，最高次项系数是常数，可以预先求出来，第二高次项的系数为等差数列，下来为2阶等差数列，3阶等差数列，（但是必须是中次项以前的系数）。公式最少个数为已给方程系数的最小公倍数。

白新岭

luyuanhong教授说的非常正确，当k>4时的确公式非常复杂，因为要想把D(n,k)用一种分类公式表达出来，需要用1至k的最小公倍数个表达式（表达式是一个（k-1)次单元函数式（系数可以为分数），不过求出的值都是正整数（或许为0），不含取整函数符号。例如k=2时有2个1次函数式；k=3时有2*3=6个2次函数式；k=4时有2*3*2=12个3次函数式；当k=5时，需要12*5=60个4次函数式；到k=5,已需要这么多，用一个含取整符号的公式完全表达出来，那是真难。不过如果能用一个近似公式表达出来的话，分子最高次项系数为1的情况下，分母应该是k!*(k-1)!,上边给出的公式都符合此规律，后边的也符合此规律，不过一般来说用一个笼统公式是无法达到精确的值，需要分情况。用多个分类公式可以精确的计算每一个D(n,k)值，但是公式个数太多，能不能找到一个普通公式呢？（当然用一个公式表达任意的D(n,k)肯定不太精确，但是可以保证数量级不差，也有90%以上的精确度，也不是一种两全齐美的方法），写式子前先设一些等式关系，以便于书写方便：设N=n+k*(k-1)/2-1,则公式为：
（N/k-1)*(N/(k-1)-2)*(N/(K-2)-3)*.....*(N/3-(K-2))*(N/2-(k-1))/(k-1)!
共k-1个小括号乘积，展开式N的最高次项为k-1次，每个小括号内N除的分母+后面的减数之和为k+1,最后除的是(k-1)的阶乘。此公式可以解决非连续系数方程的正整数解的组数问题，只需把最后除的阶乘变为所给系数的积即可。（系数必须互质）

[补充该文...]

白新岭

[这个贴子最后由白新岭在 2009/04/03 04:44pm 第 1 次编辑]

在5楼给出了m=4以前的具体公式，现在给出m=5的所有不同类的公式（即n与60相除对应的60种不同的余数情况），现在设：n=60*（i-1）+k(k从1到60为一个周期,i从1开始到无穷大，这样任何一个n唯一对应着一组（i,k),例如n=121时，求得i=3,k=1.例如n=120时，求得i=2,k=60,这时i不能等于3，等于3导致k=0,可是k没有0值，k的取值范围是1到60，i的取值，只要是大于0的整数即可。)
在上面建立n与（i,k)的关系上，任何一个表达式都是如下的形式：
a*i^4-b*i^3+c*i^2-d*i+e.
这里a为同一个值4500，即a=4500;
b为一列等差数列，当k=1时，其值为：19950；当k=2时，其值为：19950-300=19650；
以后依次类推，k=K时，第K个公式中的b=19950-300*K(1≤K≤60)。
c为一列2阶等差数列，即第K项-第（K-1）形成的新数列为等差数列，公差为15，首项为-990。现在写出来的是c的一系列值，从第1个公式到第60个公式中的c值：
(c=33132.5,32142.5,31167.5,30207.5,29262.5,28332.5,27417.5,26517.5,25632.5,24762.5,23907.5,23067.5,22242.5,21432.5,20637.5,19857.5,19092.5,18342.5,17607.5,16887.5,16182.5,15492.5,14817.5,14157.5,13512.5,12882.5,12267.5,11667.5,11082.5,10512.5,9957.5,9417.5,8892.5,8382.5,7887.5,7407.5,6942.5,6492.5,6057.5,5637.5,5232.5,4842.5,4467.5,4107.5,3762.5,3432.5,3117.5,2817.5,2532.5,2262.5,2007.5,1767.5,1542.5,1332.5,1137.5,957.5,792.5,642.5,507.5,387.5.)
接着给出的是d的一系列值（从第一个公式到第60个公式）：数字间的减号为区分符号
"（24429.5-23343.5-22286.5-21265.5-20272.5-19314.5-18383.5-17486.5-16615.5-15777.5-14964.5-14183.5-13426.5-12700.5-11997.5-11324.5-10673.5-10051.5-9450.5-8877.5-8324.5-7798.5-7291.5-6810.5-6347.5-5909.5-5488.5-5091.5-4710.5-4352.5-4009.5-3688.5-3381.5-3095.5-2822.5-2569.5-2328.5-2106.5-1895.5-1702.5-1519.5-1353.5-1196.5-1055.5-922.5-804.5-693.5-596.5-505.5-427.5-354.5-293.5-236.5-190.5-147.5-114.5-83.5-61.5-40.5-27.5）"
再给出e的一系列值（公式中的系数就全部给出来了）：
"（6747，6351，5969，5608，5260，4932，4616，4319，4033，3765，3507，3266，3034，2818，2611，2418，2233，2062，1898，1747，1602，1469，1342，1226，1115，1014，918，831，748，674，603，540，480，427，377，333，291，255，221，192，164，141，119，101，84，70，57，47，37，30，23，18，13，10，7，5，3，2，1，1。）"
相对而言这是最简单的系数公式，如果不是以n=60i+k来划分的，系数的数值会变大，我们可以用n=60i+(k-j),j从1到60时的任何一种形式取代n=60i+k，这时除了最高次项系数不变外，其余的系数都发生变化，当然总体规律不变，3次项系数为等差数列，2次项系数为2阶等差数列。

白新岭

按6楼给出的普通公式，还可以分析一下7楼一系列公式中的系数连带关系：
根据普通公式，我们可以写出m=5的普通公式，并且计算出最高次项前的系数a,以及次高次项后边的公差。
另n=60i+k代入S(n,m)=((n-1)/5-1)*((n-1)/4-2)*((n-1)/3-3)*((n-1)/2-4)/4!
                   =((n-1)/5-1)*((n-1)/4-2)*((n-1)/3-3)*((n-1)/2-4)/24
用60i+k代替n后，最高次项的系数为（60/5*60/4*60/3*60/2）/24=4500.
当k改变量为1时，其他值不动，仅是k有k+1替代，此时每个括号项分别增加-1/5，-1/4，-1/3，-1/2的改变量，对应除本括号以外的3个变量系数积，即60/5=12，60/4=15，60/3=20，60/2=30，依次由12*15*20*（-1/2）=-1800，15*20*30*（-1/5）=-1800，20*30*12*（-1/4）=-1800，30*12*15*（-1/3）=-1800，有（-1800*4）/24=-300.所以形成的次高次项的系数为等差数列。不再分析2阶等差数列系数了。

白新岭

这里有些关于整数分拆或顺序自然系数线性方程正整数解的组数内容。

白新岭

以前研究的问题是自然数域中方程解的组数问题，最近有林梦启先生的提醒，在探讨特殊自然数域中方程解的组数问题（即增加条件后的问题，条件是不能整除某些数），当研究素数域和的分布时，就会从有限个条件到无限个条件上去，也从量变到了质变，无论多条件还是无限条件仍是一类问题，总的规律没有变，在有限的条件下得到的结论，在无限的条件下仍能成立。