數(shù)論與組合數(shù)學(xué)計科0907班.ppt

1、數(shù)論與組合數(shù)學(xué),計科0907班 何劍 Email:,主講內(nèi)容,數(shù)論 解模線性方程 解模線性方程組（中國剩余定理） 歐拉函數(shù)，歐拉定理 組合數(shù)學(xué) 鴿巢原理 全排列的生產(chǎn) catalan數(shù) polya計數(shù),數(shù)論入門,解模線性方程： 求解方程 ax = b (%n) 其中a,b,n已知，求x 解法： 歐幾里德方法求gcd： gcd(a,b) = gcd(b,a%b); /循環(huán)計算式,直到b=0. 擴展歐幾里德： ax = b(%n) ax + ny = b 的整數(shù)解 設(shè) d=gcd(a,n)，則方程等價為 ax + ny = b; (a = a/d ; n = n/d ; b = b/d;需要d |

2、 b,不整除無解,如何解ax+ny = b,ax+ny=b 的解是 ax+ny=1 的解的b倍 觀察歐幾里德循環(huán)過程： ax + ny = 1 與 gcd(a,n)=gcd(n,a % n); 方程 nx+(a % n)y=1 的解與ax+ny=1的解 是否可以通過某種變換使得x=f(x),y=g(y); 答案是顯然的： y = x; x = x - a/n*y; 注意到a % n = a - a/n*n，自己演算一下就知道了,Ex_gcd(a,b,n,int ex_gcd(int a,int b,int,模線性方程組,中國剩余定理： x = b0 (mod m0) x = b1 (mod m

3、1) . x = bn-1 (mod mn-1) 當(dāng)m0,m1,.mn-1兩兩互質(zhì)時，方程有唯一解！解的范圍在0.T-1;T=m0*.*mn-1 如何解滿足中國剩余定理的方程： 記Mi=M/mi(0=in),因為gcd(Mi,mi)=1,故有二整數(shù)pi,qi滿足Mi*pi+mi*qi=1.如果記ei=Mi*pi. 那么有： ei = 0(mod mj, j!=i) 或 1(mod mj, j=i) 于是解就是,素數(shù)相關(guān)問題,歐拉函數(shù)phi(x): phi(x)=y|y *定義為 a*b % (x). 也就是一個(mod x) 下的包含乘法的群。 歐拉定理:aphi(x) = 1 (%x) a屬

4、于整數(shù)集Z 由群論中的拉格朗日定理直接可得！ 拉格朗日定理： 有限群G中任意一個元素的階o(a) | #G. o(a)定義為ao(a) % #G = a; 既a的周期 phi(x)怎么求： phi(x) = x * (1-1/fac0) * (1-1/faci) *.(1-1/facn-1) 簡單來說就是每個x的質(zhì)因子都刪掉一部分?jǐn)?shù),組合數(shù)學(xué),N個人坐在跟自己編號不同的位置上，有多少種方法？ 12個不同顏色的珠子串成一條項鏈，能夠做成多少個不同的項鏈,什么是組合數(shù)學(xué),第一個問題是經(jīng)典的錯排問題，考慮第N個人 若前N-1個人已完全錯排則有第N個人和前N-1個任意一個人換即可. 若前N-1個人未完

5、全錯排，其中有一個仍在自己位置上，則第N個人跟它換即可. 若有兩個人未錯排，則無論如何都無法完全錯排所以可得 FN=(N-1)*(FN-1+FN-2,什么是組合數(shù)學(xué),第二個問題是一個圓排列。 珠子串成一條線的排列數(shù)：12！ 除去由旋轉(zhuǎn)產(chǎn)生的重復(fù)排列：12！/12=11！ 除去由翻轉(zhuǎn)產(chǎn)生的重復(fù)排列：11！/2,存在性問題-鴿巢原理,鴿巢原理是組合數(shù)學(xué)中最簡單也是最基本的原理，也叫 Dirichlet抽屜原理。 即“若有n個鴿子巢，n+1個鴿子，則至少有一個巢內(nèi)有至少有兩個鴿子。,鴿巢原理-編程例題,POJ2356 Find a multiple 題目大意：給出n個任意的整a1,a2.an，求一段

6、連續(xù)和上s(i,j)=ai+a(i+1)+aj使得s(i,j)是n的整數(shù)倍。（N=10000,暴力枚舉,Si=a1+a2+.+ai; 暴力枚舉i,j使得(sj-si) 能整除N？ 空間效率：O(N); 時間效率：O(N2);(n=10000). 太慢了,思考,觀察Si.恰好有個N個Si,又是N的倍數(shù)，聯(lián)想到鴿巢原理！ 1)如果Si中存在一個數(shù)Sk為n的倍數(shù)，那么選前k個數(shù)即可 2)如果Si中不存在n的倍數(shù)，那么S1,S2,.Sn除以n所得的n個余數(shù)將分布在區(qū)間1,n-1中，那么必定存在i,j(ij)，使得Si mod n = Sjmod n，那么我們可以選擇ai+1+ai+2+.+aj,程序代

7、碼,include #include #define maxn 10001 int Amaxn; int Lmaxn; int main() int N,i,j,s=0; scanf(%d,if(Ls=0) printf(%dn,i-Ls); for(j=Ls+1; j=i; j+) printf(%dn,Aj); return 0; Ls=i;,鴿巢原理加強形式,令q1,q2,.,qn為正整數(shù)。若將 q1+q2+.+qn-n+1 個物體放入n個盒子內(nèi)，必有，或者第一個盒子至少有q1個物體，或者第二個盒子至少有q2個物體，.或者第n個盒子至少有qn個物體,證明,反證法：若n個盒子中任意一個盒子

8、都小于qi個物體，則物體總數(shù)不超過： (q1-1)+(q2-1)+.+(qn-1)=q1+q2+qn-n; 該數(shù)比所分發(fā)物體總數(shù)少1，因此我們斷言，對于某個盒子i，至少含有qi個物體,數(shù)學(xué)應(yīng)用,N2+1個人肩并肩地排成一條直線，總能選出n+1個人向前邁出一步，使得從左到右他們的身高是遞增（或遞減）的,證明,問題抽象成數(shù)學(xué)模型：即從有n2+1個數(shù)的實數(shù)列ai中，選出一段子序列，使其單增（或單減）。 1.我們假設(shè)不存在長度為n+1的遞增子序列，且令mk為以ak開頭的最長子序列的長度。則有1=mk=n，既m1,m2,m(n2+1)是1到n之間的n2+1個整數(shù)，則必有： m(k1)=m(k2)=m(k

9、(n+1) 其中1=k1k2.k(n+1)=n2+1,證明,又由于mk為以ak開頭的最長子序列的長度，若akikj)則必有m(ki)=m(kj)+1與m(ki)=m(kj)相矛盾，因此有a(ki)a(kj)既 a(k1)=a(k2)=.=a(k(n+1)既a(ki)為一個遞減子序列。 同理可得若無遞減子序列則必有遞增子序列,計算問題實例排列的生成,題目描述：給一個無重復(fù)項的數(shù)列pi按字典序輸出pi的所有全排列。（字典序即從第1項到第n項逐個比較大?。?例如：123 132 213 312 321,計算問題字典序法生成全排列,問題簡化：怎樣從給定的序列生成下一個恰好字典序比其大的序列。 考察數(shù)列

10、12354，發(fā)現(xiàn)末尾2項54是降序排列，則無論如何交換其中的項，只能使字典序變小。 得出結(jié)論：必然從末尾開始找到第一個pi,使得pip(i+1).既pi+1pn是最長降序。交換時必是pi與pi+1pn中某項交換 由于要使序列字典序盡可能小，則從pi右邊的各項中找一個恰好比pi大的pj,又因末尾為降序，故從左至右找到第一個比pi大的pj即可,計算問題字典序法生成全排列,由于此時pi+1.pn仍滿足降序，故將其逆轉(zhuǎn)可得目標(biāo)最小序列 例如12453逆轉(zhuǎn)成12435，則12435即為由上一個排列12354生成的排列. 這樣的規(guī)則可以保證生成的排列按照從小到大的順序生成，所以從123n開始到n321結(jié)束

11、即可生成全排列,代碼實現(xiàn),include main() FILE *fp; fp=fopen(pailie.out,w); int n,i,p100,k,j,k1,k2,l,t; long num=1; scanf(%d,代碼實現(xiàn),for(k=2;k=0,排列組合編程例題,POJ3421 X-factor Chains Given a positive integer X, an X-factor chain of length m is a sequence of integers, 1 = X0, X1, X2, , Xm = X Satisfying Xi Xi+1 and Xi | X

12、i+1 Find the maximum length of X-factor chains and the number of chains of such length,solution,可以考慮這樣一個序列： X0, X1/X0, X2/X1, , Xm/ Xm-1 這個序列中所有元素都為X的因數(shù)，且所有元素的乘積為X。那么問題可以轉(zhuǎn)換為尋找X所有的質(zhì)因數(shù)及其個數(shù)，以及由所有質(zhì)因數(shù)的構(gòu)成排列的個數(shù)。 其中的組合問題即為前面的多重集合的排列計數(shù),特殊的計數(shù)序列-Catalan數(shù),問題的提出：有2n個人排成一行進入劇場。入場費50美分。2n個人中的n個人有50分一個的分幣，n個人有1美元的紙

13、幣，售票處剛開始沒錢，有多少種列隊方法使得售票處時刻都有錢找零,特殊的計數(shù)序列-Catalan數(shù),數(shù)學(xué)模型： n個+1和n個-1構(gòu)成的2n項 a1,a2a2n 其部分和滿足 a1+a2+ak = 0 (k=1,2,32n) 這種的數(shù)列有多少個,特殊的計數(shù)序列-Catalan數(shù),利用減法原理。數(shù)列的個數(shù)等于所有的排列個數(shù)減去不滿足條件的排列個數(shù)。 其中，所有的排列個數(shù)：C(2n,n) 不滿足條件的排列中，考慮最小的k，使得部分和a1+a2+ak 0, 則有：a1+a2+ak = -1 且ak=-1,特殊的計數(shù)序列-Catalan數(shù),此時，將前k項反號，即1-1,-1-1。那么整個序列中，有n+1個1，n-1個-1，一共有C(2n,n-1)種。這種排列和不滿足條件的n個1和-1的排列是一一對應(yīng)的。 那么滿足條件的排列數(shù)：C(2n,n)-C(2n,n-1)= C(2n,n)/(n+1,Catalan數(shù)的一個應(yīng)用,凸多邊形的劃分：將一個凸多邊形通過其對角線的分割使其成為若干個三角形，問有多少種分法,solution,確定一條基