Q2: 3x+4y+6z=2003 有多少正整數解?
Q3: ax+by+cz= k, 有多少正整數解? (請寫成N=f(k,a,b,c)的形式)
[數學]How many integer solutions?
[數學]How many integer solutions?
由 --- 於 星期四 四月 10, 2003 8:52 pm
Q1: 3x+4y+5z=2003 有多少正整數解?
Q2: 3x+4y+6z=2003 有多少正整數解?
Q3: ax+by+cz= k, 有多少正整數解? (請寫成N=f(k,a,b,c)的形式)
Q2: 3x+4y+6z=2003 有多少正整數解?
Q3: ax+by+cz= k, 有多少正整數解? (請寫成N=f(k,a,b,c)的形式)
-
--- - 訪客
由 --- 於 星期四 四月 10, 2003 11:28 pm
Q1: 3x+4y+5z=2003 有多少正整數解?
---
generating function (^_^ my favorate method)
" 3x+4y+5z=2003 有多少正整數解? " equals to "3x+4y+5z=2003-3-4-5=1991 有多少non-negative整數解? "
for 3x+4y+5z=k 有ak 個 non-negiative整數解? "
we can get the generating function for k:
f(x)= a0+a1*x+a2*x^2+....
=1/(1-x^3)(1-x^4)(1-x^5)
=1/(1-x)^3/(1+x+xx)/(1+xx)/(1+x)/(1+x+xx+xxx+xxxx)
to partial-fractionize f(x),
let w1=cos(2pi/3)+isin(2pi/3), w2=cos(2pi/3)-isin(2pi/3)
q1= cos(2pi/5)+isin(2pi/5), q2=q1^2, q3=q1^3, q4=q1^4
then
f(x)=1/(1-x)^3/(1-w1x)(1-w2x)/(1+xx)/(1+x)/(1+x+xx+xxx+xxxx)
=-590/3600(1-x)+270/(1-x)^2 /3600+1/(1-x)^3 /60
+t/(1+x)
+m(1/(1-w1x)+1/(1-w2x))+n(1/(1+ix)+1/(1-ix))
+p(1/(1-q1x)+1/(1-q4x))+r(1/(1-q2x)+1/(1-q3x))
the major part of ak would be:
-590/3600+(k+1)(k+2)/2/60
+270(k+1)/3600
so, to give an estimation: N~ -59/360+1992*1993/120+1992*3/40 ~ 33233.03611 33233
If you want the precise answer, calculate t,m,n,p,r, then add
t*(-1)^k+2m*cos(2kpi/3)+2n*cos(kpi/2)+2p*cos(2kpi/5)+2r*cos(4kpi/5)
---
generating function (^_^ my favorate method)
" 3x+4y+5z=2003 有多少正整數解? " equals to "3x+4y+5z=2003-3-4-5=1991 有多少non-negative整數解? "
for 3x+4y+5z=k 有ak 個 non-negiative整數解? "
we can get the generating function for k:
f(x)= a0+a1*x+a2*x^2+....
=1/(1-x^3)(1-x^4)(1-x^5)
=1/(1-x)^3/(1+x+xx)/(1+xx)/(1+x)/(1+x+xx+xxx+xxxx)
to partial-fractionize f(x),
let w1=cos(2pi/3)+isin(2pi/3), w2=cos(2pi/3)-isin(2pi/3)
q1= cos(2pi/5)+isin(2pi/5), q2=q1^2, q3=q1^3, q4=q1^4
then
f(x)=1/(1-x)^3/(1-w1x)(1-w2x)/(1+xx)/(1+x)/(1+x+xx+xxx+xxxx)
=-590/3600(1-x)+270/(1-x)^2 /3600+1/(1-x)^3 /60
+t/(1+x)
+m(1/(1-w1x)+1/(1-w2x))+n(1/(1+ix)+1/(1-ix))
+p(1/(1-q1x)+1/(1-q4x))+r(1/(1-q2x)+1/(1-q3x))
the major part of ak would be:
-590/3600+(k+1)(k+2)/2/60
+270(k+1)/3600
so, to give an estimation: N~ -59/360+1992*1993/120+1992*3/40 ~ 33233.03611 33233
If you want the precise answer, calculate t,m,n,p,r, then add
t*(-1)^k+2m*cos(2kpi/3)+2n*cos(kpi/2)+2p*cos(2kpi/5)+2r*cos(4kpi/5)
-
--- - 訪客
由 --- 於 星期五 四月 11, 2003 11:23 pm
Px+Qy+Rz=A
When P,Q,R兩兩互質, N~round(A*(A-P-Q-R)/2PQR);相當準確喔
Ex:
A=343
P=9,Q=5,R=2
N=round(A*(A-P-Q-R)/2PQR)=623
實際解也=623組.
Ex:
A=500
P=11,Q=5,R=3
N=round(A*(A-P-Q-R)/2PQR)=729
實際解也=729組.
--------------------------------------------------------------------------------
More:
(1)
P1X1+P2X2+P3X3+...+PkXk=A
When P1,P2,P3,..Pk兩兩互質, N~round((A-(P1+P2+P3+...+Pk)/2)^(k-1))/(k-1)!/P1P2P3...Pk)
(2)
If you want a accurate solution but not an estimation, you need "generation functon" to deal with.
Ex:
A=343
P=8,Q=5,R=2
estimated N=round((A-(P+Q+R)/2)^2/2PQR)=703
實際解=714組.
let w=cos(2pi/5)+isin(2pi/5)
let u=cos(pi/4)+isin(pi/4)
generation functon F(x)=1/(1-x^2)(1-x^5)(1-x^8)
=1/(1-x)^3/(1+x)^2/(1-w)(1-ww)(1-www)(1-wwww)/(1+i)(1-i)(1-u)(1-iu)(1+u)(1+iu)
部分分式化...
=a/(1-x)+b/(1-x)^2+c/(1-x^3)+d/(1+x)+e/(1+x)^2+f/(1-w)+g/(1-ww)+h/(1-www)+i/
(1-wwww)+j/(1+i)+k/(1-i)+l/(1-u)+m/(1-iu)+n’/(1+u)+o/(1+iu)
then
N(n)=a+b*(n+1)+c*(n+1)(n+2)/2!+d*(-1)^n)+e*(-1)^n*(n+1)+f*w^n+g*w^2n+h*w^3n+
i*w^4n+j*(-i)^n+k*i^n+l*u^n+m*(iu)^n+n’*(-u)^n+o/(-iu)^n
n再用343代入
--------------------------------------------------------------------------------
so, N(n)的主項=a+b*(n+1)+c*(n+1)(n+2)/2!+d*(-1)^n)+e*(-1)^n*(n+1)
error <｜f｜+｜g｜+｜h｜+｜i｜+...+｜o｜
--------------------------------------------------------------------------------
we can find that the "main variation item" is (-1)^n * (n+1)*e
so we can calculate c only, as a correction.
c=1/(1-(-1))^3/(1-1+1-1+1)/(1+1)/(1+1)=1/32
then the estimation N=round((A-(8+5+2)/2)^2/2/2/5/8 +(-1)^(A-(8+5+2))*(A-(8+5+2)+1)/32)
For calculate A=343, n=A-P-Q-R=328
n+1=329
then the estimation N=round((A-(8+5+2)/2)^2/2/2/5/8 +(-1)^(A-(8+5+2))*(A-
(8+5+2)+1)/32)=714; error=0
-------------------
for calculate A=8888, P=6,Q=5,R=27
n=A-P-Q-R=8850
F(x)=1/(1-x)^3/(1+x)/(1+x+xx)^2/(1+x+xx+xxx+xxxx)/(1+x^3+x^6+…+x^24)
main N=(A-(6+5+27)/2)^2/2/6/5/27=48555.037
F(x)=a/(1-xww)^2+b/(1-wx)^2)+…
main variation=cos(pi/6+pi*2n/3)*(n+1)/6/27/cos(pi/6)
estmated N=round(mainN+main variation)=(round(48555.037+54.636)=54610
error=0
------------------
一班而言, 以 Nmain=(A-sigma(Pi)/2)^(k-1)/k!(P1P2…Pk)
加上generation function 算出main variation項, 就可以得到絕大多數誤差不超過1的公式了
--------------------------------------------------------------------------------
Game-over.
喵的Excel說:"看不懂的不要問.看的懂的也不要問."
喵說:"看的懂又看不懂的才可以問"
喵的IE說:"問也沒用"
When P,Q,R兩兩互質, N~round(A*(A-P-Q-R)/2PQR);相當準確喔
Ex:
A=343
P=9,Q=5,R=2
N=round(A*(A-P-Q-R)/2PQR)=623
實際解也=623組.
Ex:
A=500
P=11,Q=5,R=3
N=round(A*(A-P-Q-R)/2PQR)=729
實際解也=729組.
--------------------------------------------------------------------------------
More:
(1)
P1X1+P2X2+P3X3+...+PkXk=A
When P1,P2,P3,..Pk兩兩互質, N~round((A-(P1+P2+P3+...+Pk)/2)^(k-1))/(k-1)!/P1P2P3...Pk)
(2)
If you want a accurate solution but not an estimation, you need "generation functon" to deal with.
Ex:
A=343
P=8,Q=5,R=2
estimated N=round((A-(P+Q+R)/2)^2/2PQR)=703
實際解=714組.
let w=cos(2pi/5)+isin(2pi/5)
let u=cos(pi/4)+isin(pi/4)
generation functon F(x)=1/(1-x^2)(1-x^5)(1-x^8)
=1/(1-x)^3/(1+x)^2/(1-w)(1-ww)(1-www)(1-wwww)/(1+i)(1-i)(1-u)(1-iu)(1+u)(1+iu)
部分分式化...
=a/(1-x)+b/(1-x)^2+c/(1-x^3)+d/(1+x)+e/(1+x)^2+f/(1-w)+g/(1-ww)+h/(1-www)+i/
(1-wwww)+j/(1+i)+k/(1-i)+l/(1-u)+m/(1-iu)+n’/(1+u)+o/(1+iu)
then
N(n)=a+b*(n+1)+c*(n+1)(n+2)/2!+d*(-1)^n)+e*(-1)^n*(n+1)+f*w^n+g*w^2n+h*w^3n+
i*w^4n+j*(-i)^n+k*i^n+l*u^n+m*(iu)^n+n’*(-u)^n+o/(-iu)^n
n再用343代入
--------------------------------------------------------------------------------
so, N(n)的主項=a+b*(n+1)+c*(n+1)(n+2)/2!+d*(-1)^n)+e*(-1)^n*(n+1)
error <｜f｜+｜g｜+｜h｜+｜i｜+...+｜o｜
--------------------------------------------------------------------------------
we can find that the "main variation item" is (-1)^n * (n+1)*e
so we can calculate c only, as a correction.
c=1/(1-(-1))^3/(1-1+1-1+1)/(1+1)/(1+1)=1/32
then the estimation N=round((A-(8+5+2)/2)^2/2/2/5/8 +(-1)^(A-(8+5+2))*(A-(8+5+2)+1)/32)
For calculate A=343, n=A-P-Q-R=328
n+1=329
then the estimation N=round((A-(8+5+2)/2)^2/2/2/5/8 +(-1)^(A-(8+5+2))*(A-
(8+5+2)+1)/32)=714; error=0
-------------------
for calculate A=8888, P=6,Q=5,R=27
n=A-P-Q-R=8850
F(x)=1/(1-x)^3/(1+x)/(1+x+xx)^2/(1+x+xx+xxx+xxxx)/(1+x^3+x^6+…+x^24)
main N=(A-(6+5+27)/2)^2/2/6/5/27=48555.037
F(x)=a/(1-xww)^2+b/(1-wx)^2)+…
main variation=cos(pi/6+pi*2n/3)*(n+1)/6/27/cos(pi/6)
estmated N=round(mainN+main variation)=(round(48555.037+54.636)=54610
error=0
------------------
一班而言, 以 Nmain=(A-sigma(Pi)/2)^(k-1)/k!(P1P2…Pk)
加上generation function 算出main variation項, 就可以得到絕大多數誤差不超過1的公式了
--------------------------------------------------------------------------------
Game-over.
喵的Excel說:"看不懂的不要問.看的懂的也不要問."
喵說:"看的懂又看不懂的才可以問"
喵的IE說:"問也沒用"
-
--- - 訪客
由 Raceleader 於 星期五 四月 11, 2003 11:42 pm
但Meowth要開始改一些習慣
1. 要利用容易的方法解,而非最喜歡但無人明的方法,這等於沒有去解
2. 分享時要直接,不要收錢或隱藏文章
3. 解釋仍不足,因為沒有考慮其他人的程度,要讓人明白便是分享的目的
1. 要利用容易的方法解,而非最喜歡但無人明的方法,這等於沒有去解
2. 分享時要直接,不要收錢或隱藏文章
3. 解釋仍不足,因為沒有考慮其他人的程度,要讓人明白便是分享的目的
-
Raceleader - 訪客
由 --- 於 星期六 四月 12, 2003 12:06 am
Raceleader 寫到:但Meowth要開始改一些習慣
1. 要利用容易的方法解,而非最喜歡但無人明的方法,這等於沒有去解
2. 分享時要直接,不要收錢或隱藏文章
3. 解釋仍不足,因為沒有考慮其他人的程度,要讓人明白便是分享的目的
-------------------
喵的Excel說:"看不懂的不要問.看的懂的也不要問."
喵說:"看的懂又看不懂的才可以問"
喵的IE說:"問也沒用"
-------------------
要看generating function 我的解釋的,請到 數學研究室 精華區/討論區精華 /Xie/離散數學/生成函數
http://tw.club.yahoo.com/clubs/mathexperiment/
But I suggest you high school students to buy a book (離散數學初步,九章出版) to read.
-------------------
p.s. 隱藏文章 是要大家先想想解法. 直接看答案 is not so fun, right?
p.s. 解釋仍不足... sorry, I'm not good at languages.
-
--- - 訪客
Re: [數學]How many integer solutions?
由 --- 於 星期日 四月 13, 2003 2:25 pm
Meowth 寫到:Q1: 3x+4y+5z=2003 有多少正整數解?
According to the estimation:
round((2003-(3+4+5)/2)^2/2!/3/4/5)=33233
error=0
-
--- - 訪客