组合数学在数论中的应用实例.doc

组合数学在数论中的应用实例摘要：本文将组合数学中的容斥原理和递归关系应用到数论中,讨论了数组整除性的判定和整除的计数;Euler函数的计数和质数个数的计数问题。关键词：容斥原理;递归关系;整除;Euler函数;质数我们知道,在组合数学中,容斥原理(又称包含排斥原理)和递归关系是解决组合计数问题的一个重要工具和方法。将这一重要工具和方法应用到数论中,对于数组整除性的判定和整除的计数;Euler函数的计数和质数个数的计数,都会带来很大方便。下面,首先简要介绍容斥原理、常系数线性齐次递归关系的建立和迭代解法,然后给出几个应用实例。1容斥原理与常系数线性齐次递归关系简介1.1容斥原理设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 容斥原理还有另一种叙述形式,即设S是有限集合,P1,P2,Pn是n个性质,Ai是S中具有性质Pi的元素的集合,A-i是S中不具有性质Pi的元素的集合(以上i=1,2,n)。对于任意k(1kn)个正整数i1,i2,ik(1i1i2ikn), Ai1Ai2Aik 表示S中同时具有性质Pi1,Pi2,Pik的元素个数, A-1A-2A-n 表示S中不具有性质P1,P2,Pn中任何一个性质的元素个数,即 A-1A-2A-n = S +nk=1(-1)k1i1i2ikn Ai1Ai2Aik 1.2常系数线性齐次递归关系的解法设ann0是一数列,通项an与其前面若干项的关系式通常称为关于该数列通项的一个递归关系。设c1,c2,ck是k个常数,且ck0,则递归关系an=c1an-1+c2an-2+ckan-k(nk)称为k阶常系数线性齐次递归关系。称方程xk=c1xk-1+c2xk-2+ck-1x+ck为此递归关系的特征方程。由代数基本定理,这个k次方程在复数域内有k个根。设q1,q2,qt为其全部不同的根,重数分别是r1,r2,rt(显然r1+r2+rt=k),则此数列的通项为:an=(b11+b12n+b1r1nr1-1)qn1+(b21+b22n+b2r2nr2-1)qn2+(bt1+bt2n+btrtnrt-1)qnt其中诸bij(共有k个)是待定系数,只需将数列an开始的k项初值代入即可确定出这些系数,从而最终得到数列an的通项公式。反之,由数列an的通项公式也可求出关于an的递归关系式。2数列ann0的整除性的判定和整除的计数整除性的判定是数论中经常遇到的问题。在数论中利用同余理论去解答此类问题是常用的方法之一。本文主要讨论数列ann0的各项可被某一整数整除的判定问题。利用递归关系的解法,可以给出上述问题的解答。读者可以通过下面的例题举一返三总结出解答此类问题的方法。例1:证明数列ann0=11n+2+122n+1的各项能被133整除。证法1:利用数论中的同余理论证明由于133等于两个质数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:利用递归关系的解法证明因为an=11n+2+122n+1=12111n+12144n,而11+144=155,11144=1584所以x1=11,x2=144是方程x2-155x+1584=0的两个根,从而有递归关系an=155an-1-1584an-2(n2)又因为a0=121+12=133a1=12111+12144=3059=13323a0和a1都能被133整除,由递归关系式可知an(n=0,1,2,)均能被133整除。证毕7我们还可以利用容斥原理去解决一个整除的计数问题。设a1,a2,an及N都是正整数,如何计算出从1到N的N个整数中同时能被a1,a2,an中某几个指定的数整除的整数个数;以及不能被a1,a2,an中的任何一个整除的整数个数呢?容斥原理直接给出了这个问题的解答。令S=1,2,N,设sS。若ai s,则称s具有性质pi,又设Ai是S中具有性质Pi的元素集合,A-i是S中不具有性质Pi的元素集合(以上i=1,2,n)。显然, Ai1Ai2Aik 就是S中同时具有性质Pi1,Pi2,Pik的元素个数,(以上1i1i2ikn,1kn),而 A-1A-2A-n 就是S中不具有性质P1,P2,Pn中任何一个性质的元素个数。由于一个整数能同时被ai1,ai2,aik整除当且仅当这个整数能被它们的最小公倍数lcm(ai1,ai2,aik)整除,所以 Ai1Ai2Aik =Nlcm(ai1,ai2,aik)上式中Nlcm(ai1,ai2,aik)表示其值为不大于Nlcm(ai1,ai2,aik)的最大整数。由容斥原理可得出 A-1A-2A-n =N+nk=1(-1)k1i1i2ikn Ai1Ai2Aik =N+nk=1(-1)k1i1i2iknNlcm(ai1,ai2,aik)3Euler函数的计数和质数个数的计数Euler函数是数论中的一个重要函数。设n为自然数,以(n)表示不大于n且与n互质的自然数个数,这个(n)就称为Euler函数。例如(12)=4,(13)=12,(36)=12。若P为质数,则显然有(P)=P-1。若n是一个较大的合数,则(n)的计数就不那么容易了。然而,利用容斥原理(n)的计数问题就可以很快得到解决。设n(n2)为自然数,P1,P2,Pm是n的全部质因数,r是任一不大于n的自然数。r与n互质当且仅当r不能被P1,P2,Pm中的任一个整除。因此,(n)等于由1到n的n个整数中不能被P1,P2,Pm中的任一个整除的整数个数。由容斥原理可直接得到(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利用这一结果,可以很容易验证(12)=4,(13)=12,(36)=12。设n是自然数,以(n)表示不大于n的质数的个数。虽然目前尚未找到(n)的计数公式,但是利用容斥原理我们可以得到一种求(n)的方法。设p1,p2,pm是不大于n的全部质数。令S=1,2,n,任取sS,由数论知识可知,s是质数当且仅当要么s是p1,p2,pm中之一;要么s1且不能被p1,p2,pm中的任一个整除。由容斥原理,S中不能被p1,p2,pm中的任一个整除的整数个数是n+mk=1(-1)k1i1i2ikmnpi1pi2pik其中1是适合上述条件的一个数,但1不是质数,因此要减去1。p1,p2,pm这m个数不适合上述条件。但它们又都是不大于n的质数,因此还要加上m。这样一来就可求出(n)的值。(n)=m-1+n+mk=1(-1)k1i1i2ikmnpi1pi2pik例2:求(42)解:不大于42的全部质数有3个:2,3,5,所以(42)=3-1+42-422+423+425+4223+4225+4235-42235=13经验证知,不大于42的质数有2,3,5,7,