4.4篩法原理應用_第1頁
4.4篩法原理應用_第2頁
4.4篩法原理應用_第3頁
全文預覽已結束

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

4.4篩法原理應用篩法公式在初等數論中有很多應用，下面給出一些有關因式分解的定理。設x為實數，[x]表示小于或等于x的最大整數。例如[2.8]=2,[3.4]=3等。定理4.5設n為正整數。為小于n的正整數，且，則使得，且的正整數k的個數為證明令S是n個正整數1,2,…,n的集合，性質P(i)是指S中元素能被除盡。也就是說表示S中能被除盡的元素個數，因而，由于表示S中能被整除的元素個數，因而表示能被整除的元素個數，因而由篩法公式如果n為正整數，歐拉函數表示與n互質（比n小）的正整數個數，即滿足0<k<n,(k,n)=1的元素k的個數。由上述定理可得以下推論。推論設n為正整數，則這里p取遍n的所有素數因子。證明由定理4.5,把n提出來后，括號里的式子與相同。最后我們利用篩法公式計算“積和式”（permanent）.設m行n列矩陣為定義A的積和式為這里取遍1,2,…,n的所有排列[共有n(n-1)…（n-m+1）]項。所有項都是正號（這與行列式不同）。現在我們設Ar是A中有r個列用0代替所得的矩陣；S（Ar）表示矩陣Ar的每一行元素和的乘積，即第一行的和第二行的和…第m行的和；的和（即取Ar的所有可能選擇）。現在計算當n=m時，矩陣A的積和式時也不難計算）。設S的所有下列元素乘積的和為（4-4-1）其中i1,i2,…,in是1,2,…,n的任意可重復排列（共nn項）。顯然，S(A)是這nn個元素的和。現在設P(1)表示這樣的性質：在（4-4-1）式中i1,i2,…,in這n個數碼中沒有1出現；…P(i)表示這樣的性質：在（4-4-1）式中i1,i2,…,in中沒有數碼i出現;P(i)P(j)表示i1,i2,…,in中沒有數碼i與j出現。具有一個性質P(i)的元素顯然是中的一項，具有兩個性質P(i)P(j)的元素是中的一項，…，per(A)顯然是S中沒有任何性質P(i)的元素和，由篩法原理得如果A中元素全為1，則當矩陣A的對角線元素全為0，其余元素全為1時=擾亂排列總數因為在乘積（否則乘積為0）積和式在初等排列組合中有很多應用。例如，計算矩陣的積和式per(A),實際上是：排列i1,i2,i3中i1不能取3的排列數。Per(A)=4.而矩陣的積和式per(B)卻是排列i1,i2,i3中i1不能取3，i2不能取1的排列數。per(B)=3練習4.40011100111100111100

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論