組合數(shù)學(xué)在數(shù)論中的應(yīng)用實例.doc

組合數(shù)學(xué)在數(shù)論中的應(yīng)用實例摘要：本文將組合數(shù)學(xué)中的容斥原理和遞歸關(guān)系應(yīng)用到數(shù)論中,討論了數(shù)組整除性的判定和整除的計數(shù);Euler函數(shù)的計數(shù)和質(zhì)數(shù)個數(shù)的計數(shù)問題。關(guān)鍵詞：容斥原理;遞歸關(guān)系;整除;Euler函數(shù);質(zhì)數(shù)我們知道,在組合數(shù)學(xué)中,容斥原理(又稱包含排斥原理)和遞歸關(guān)系是解決組合計數(shù)問題的一個重要工具和方法。將這一重要工具和方法應(yīng)用到數(shù)論中,對于數(shù)組整除性的判定和整除的計數(shù);Euler函數(shù)的計數(shù)和質(zhì)數(shù)個數(shù)的計數(shù),都會帶來很大方便。下面,首先簡要介紹容斥原理、常系數(shù)線性齊次遞歸關(guān)系的建立和迭代解法,然后給出幾個應(yīng)用實例。1容斥原理與常系數(shù)線性齊次遞歸關(guān)系簡介1.1容斥原理設(shè)S是有限集合,Ai S(i=1,2,n,n2)則 ni=1Ai =( A1 + A2 + An )-( A1A2 + A1A3 + An-1An )+(-1)n-1 A1A2An =nk=1(-1)k-11i1i2ikn Ai1Ai2Aik 這就是容斥原理。顯然,容斥原理也可以寫成 S-ni=1Ai = S +nk=1(-1)k1i1i2ikn Ai1Ai2Aik 容斥原理還有另一種敘述形式,即設(shè)S是有限集合,P1,P2,Pn是n個性質(zhì),Ai是S中具有性質(zhì)Pi的元素的集合,A-i是S中不具有性質(zhì)Pi的元素的集合(以上i=1,2,n)。對于任意k(1kn)個正整數(shù)i1,i2,ik(1i1i2ikn), Ai1Ai2Aik 表示S中同時具有性質(zhì)Pi1,Pi2,Pik的元素個數(shù), A-1A-2A-n 表示S中不具有性質(zhì)P1,P2,Pn中任何一個性質(zhì)的元素個數(shù),即 A-1A-2A-n = S +nk=1(-1)k1i1i2ikn Ai1Ai2Aik 1.2常系數(shù)線性齊次遞歸關(guān)系的解法設(shè)ann0是一數(shù)列,通項an與其前面若干項的關(guān)系式通常稱為關(guān)于該數(shù)列通項的一個遞歸關(guān)系。設(shè)c1,c2,ck是k個常數(shù),且ck0,則遞歸關(guān)系an=c1an-1+c2an-2+ckan-k(nk)稱為k階常系數(shù)線性齊次遞歸關(guān)系。稱方程xk=c1xk-1+c2xk-2+ck-1x+ck為此遞歸關(guān)系的特征方程。由代數(shù)基本定理,這個k次方程在復(fù)數(shù)域內(nèi)有k個根。設(shè)q1,q2,qt為其全部不同的根,重數(shù)分別是r1,r2,rt(顯然r1+r2+rt=k),則此數(shù)列的通項為:an=(b11+b12n+b1r1nr1-1)qn1+(b21+b22n+b2r2nr2-1)qn2+(bt1+bt2n+btrtnrt-1)qnt其中諸bij(共有k個)是待定系數(shù),只需將數(shù)列an開始的k項初值代入即可確定出這些系數(shù),從而最終得到數(shù)列an的通項公式。反之,由數(shù)列an的通項公式也可求出關(guān)于an的遞歸關(guān)系式。2數(shù)列ann0的整除性的判定和整除的計數(shù)整除性的判定是數(shù)論中經(jīng)常遇到的問題。在數(shù)論中利用同余理論去解答此類問題是常用的方法之一。本文主要討論數(shù)列ann0的各項可被某一整數(shù)整除的判定問題。利用遞歸關(guān)系的解法,可以給出上述問題的解答。讀者可以通過下面的例題舉一返三總結(jié)出解答此類問題的方法。例1:證明數(shù)列ann0=11n+2+122n+1的各項能被133整除。證法1:利用數(shù)論中的同余理論證明由于133等于兩個質(zhì)數(shù)7和19的乘積,因此只要11n+2+122n+1能被7和19整除,則一定能被133整除。通項an可寫成為an=11n+2+122n+1=12111n+12144n。因為1217,14411(mod19),所以11n+2+122n+1711n+1211n1911n0(mod19),即19 11n+2+122n+1。而1212,114,125,1444(mod7),所以11n+2+122n+124n+54n74n0(mod7),即7 11n+2+122n+1。從而得到133 11n+2+122n+1。證畢證法2:利用遞歸關(guān)系的解法證明因為an=11n+2+122n+1=12111n+12144n,而11+144=155,11144=1584所以x1=11,x2=144是方程x2-155x+1584=0的兩個根,從而有遞歸關(guān)系an=155an-1-1584an-2(n2)又因為a0=121+12=133a1=12111+12144=3059=13323a0和a1都能被133整除,由遞歸關(guān)系式可知an(n=0,1,2,)均能被133整除。證畢7我們還可以利用容斥原理去解決一個整除的計數(shù)問題。設(shè)a1,a2,an及N都是正整數(shù),如何計算出從1到N的N個整數(shù)中同時能被a1,a2,an中某幾個指定的數(shù)整除的整數(shù)個數(shù);以及不能被a1,a2,an中的任何一個整除的整數(shù)個數(shù)呢?容斥原理直接給出了這個問題的解答。令S=1,2,N,設(shè)sS。若ai s,則稱s具有性質(zhì)pi,又設(shè)Ai是S中具有性質(zhì)Pi的元素集合,A-i是S中不具有性質(zhì)Pi的元素集合(以上i=1,2,n)。顯然, Ai1Ai2Aik 就是S中同時具有性質(zhì)Pi1,Pi2,Pik的元素個數(shù),(以上1i1i2ikn,1kn),而 A-1A-2A-n 就是S中不具有性質(zhì)P1,P2,Pn中任何一個性質(zhì)的元素個數(shù)。由于一個整數(shù)能同時被ai1,ai2,aik整除當(dāng)且僅當(dāng)這個整數(shù)能被它們的最小公倍數(shù)lcm(ai1,ai2,aik)整除,所以 Ai1Ai2Aik =Nlcm(ai1,ai2,aik)上式中Nlcm(ai1,ai2,aik)表示其值為不大于Nlcm(ai1,ai2,aik)的最大整數(shù)。由容斥原理可得出 A-1A-2A-n =N+nk=1(-1)k1i1i2ikn Ai1Ai2Aik =N+nk=1(-1)k1i1i2iknNlcm(ai1,ai2,aik)3Euler函數(shù)的計數(shù)和質(zhì)數(shù)個數(shù)的計數(shù)Euler函數(shù)是數(shù)論中的一個重要函數(shù)。設(shè)n為自然數(shù),以(n)表示不大于n且與n互質(zhì)的自然數(shù)個數(shù),這個(n)就稱為Euler函數(shù)。例如(12)=4,(13)=12,(36)=12。若P為質(zhì)數(shù),則顯然有(P)=P-1。若n是一個較大的合數(shù),則(n)的計數(shù)就不那么容易了。然而,利用容斥原理(n)的計數(shù)問題就可以很快得到解決。設(shè)n(n2)為自然數(shù),P1,P2,Pm是n的全部質(zhì)因數(shù),r是任一不大于n的自然數(shù)。r與n互質(zhì)當(dāng)且僅當(dāng)r不能被P1,P2,Pm中的任一個整除。因此,(n)等于由1到n的n個整數(shù)中不能被P1,P2,Pm中的任一個整除的整數(shù)個數(shù)。由容斥原理可直接得到(n)=n+mk=1(-1)k1i1i2ikmnlcm(pi1,pi2,pik)=n+mk=1(-1)k1i1i2ikmnpi1pi2pik=n-np1+np2+npm+np1p2+np1p3+npm-1pm+(-1)mnp1p2pm=n1-1p11-1p21-1pm利用這一結(jié)果,可以很容易驗證(12)=4,(13)=12,(36)=12。設(shè)n是自然數(shù),以(n)表示不大于n的質(zhì)數(shù)的個數(shù)。雖然目前尚未找到(n)的計數(shù)公式,但是利用容斥原理我們可以得到一種求(n)的方法。設(shè)p1,p2,pm是不大于n的全部質(zhì)數(shù)。令S=1,2,n,任取sS,由數(shù)論知識可知,s是質(zhì)數(shù)當(dāng)且僅當(dāng)要么s是p1,p2,pm中之一;要么s1且不能被p1,p2,pm中的任一個整除。由容斥原理,S中不能被p1,p2,pm中的任一個整除的整數(shù)個數(shù)是n+mk=1(-1)k1i1i2ikmnpi1pi2pik其中1是適合上述條件的一個數(shù),但1不是質(zhì)數(shù),因此要減去1。p1,p2,pm這m個數(shù)不適合上述條件。但它們又都是不大于n的質(zhì)數(shù),因此還要加上m。這樣一來就可求出(n)的值。(n)=m-1+n+mk=1(-1)k1i1i2ikmnpi1pi2pik例2:求(42)解:不大于42的全部質(zhì)數(shù)有3個:2,3,5,所以(42)=3-1+42-422+423+425+4223+4225+4235-42235=13經(jīng)驗證知,不大于42的質(zhì)數(shù)有2,3,5,7,