• /  19
  • 下載費用: 14.9積分  

組合數學之容斥原理.ppt

'組合數學之容斥原理.ppt'
組合數學 容斥原理1一. 引言●容斥原理所研究的問題是與若干有 限集的交、并或差有關的計數. ●在實際中, 有時要計算具有某種性質的元素個數. 例如: 某單位舉辦一個外語培訓班, 開設英語, 法語兩門課. 2●設U為該單位所有人集合, A,B分別為 學英語, 法語人的集合, 如圖所示. ●學兩門外語的人數為|A?B|, 只學一門外語的人數為|A?B|-|A?B|, 沒有參加學習的人數為|U|-|A?B|. 3在一些計數問題中, 經常遇到間接計算一個集合中具有某種性質的元素個數比起直接計算來得簡單. 例如: 計算1到700之間不能被7整除的整數個數. 先計算1到700之間能被7整除的整數個數=700/ 7=100, 所以1到700之間不能被7整除的整數個數=700-100=600. 4上面舉的間接計數的例子是利用了如下原理:如果A是集合S的子集, 則A中的元素個數等于S中的元素個數減去不在A中的元素個數, 這個原理可寫成:5● 原理的重要推廣, 稱之為容斥原理,并且將它運用到若干問題上去, 其中包括: 錯位排列、 有限制的排列、 禁位排列和 棋陣多項式等.6DeMorgan定理: 設A, B為全集U的任意兩個子集, 則DeMorgan定理的推廣: 設A1,A2,?,An為U的子集, 則二. 容斥原理7證明從略abaUbaUb=a∩ba=u-a=b-aUbb=u-b=a-aUbb-aUb∩a-aUb=u-aUb=aUb81. 兩個集合的容斥原理 設A和B是分別具有性質P1和P2的元素的集合, 則例6.1 求1到500之間能被5或7整除的正整數個數. 解 設A為被5整除的整數集合, B為被7整除的整數集合, 用[x]表示x的整數部分, 則有9同時被5和7整除的整數個數故能被5或7整除的整數個數102. 三個集合上的容斥原理設A, B, C為任意三個集合, 則有3. n個集合上的容斥原理: 設A1,A2,?,An是有限集合, 則有114. 集合n中不具有a1,a2,a3…之一元素的個數為(余集形式)12例求在1到10000的整數中不能被4,5,6任意一個整除的數的個數.解:令Ai(i=4,5,6)表示1到10000的整數中能被i整 除的數的個數,則13三. 容斥原理的應用實例1. 錯排問題 利用容斥原理很容易理解錯排數列通項公式的組合意義. 14(1..n)的錯位排列個數記為Dn. 結論如下:可以用容斥原理證明: 設S={1,2,3,?,n}的集合, S0為S的全排列,則s0=n! . 令Aj表示排列1,2?n中使j位置上的元素恰好是j的排列的集合, j=1,2,?,n. 則排列12?n的所有錯位排列組成集合:15?Aj?=(n-1)!, j=1,2,3,?,n.?Ai?Aj?=(n-2)!, i,j=1,2,3,?,n, 但i?j. 對于任意整數k且1?k?n, 則有因為{1,2,3,?,n}的k組合為C(n,k)個, 應用容斥原理得到:1617課堂思考題-被毀壞的玉米地 問題描述:“哈姆!外星人又在那了!”。埃塞和哈姆他們的玉米地是長方形的。每年在豐收之前,他們的玉米地都會很奇怪地遭到毀壞(據埃塞說是外星人干的)。所有破壞的地方都是以1米為半徑的圓。哈姆發現,如果在玉米地上建立一個適當的直角坐標系的話,那些圓心的坐標將都為整數。萬幸的是,埃塞和哈姆有玉米保險,但必須把損壞的面積統計出來。輸入文件(CROP.IN):輸入文件的第一行為一個整數N(O<N<=200),表示圓圈的個數。以下N行每行有兩個整數x和y,由空格分開,代表圓心坐標。數據中不存在兩個完全重合的圓。輸出文件(CROP.OUT):輸出統計出的總面積,四舍五入到小數點后4位。(Pi = 3.1415926535)輸入輸出樣例:CROP.IN20 01 0CROP.OUT5.054818選做題:孿生項鏈19
關 鍵 詞:
組合數學 原理
 天天文庫所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:組合數學之容斥原理.ppt
鏈接地址: http://www.476824.live/p-51497358.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服點擊這里,給天天文庫發消息,QQ:1290478887 - 聯系我們

本站為“文檔C2C交易模式”,即用戶上傳的文檔直接賣給(下載)用戶,本站只是中間服務平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有【成交的100%(原創)】。本站是網絡服務平臺方,若您的權利被侵害,侵權客服QQ:1290478887 歡迎舉報。

[email protected] 2017-2027 http://www.476824.live 網站版權所有

粵ICP備19057495號 

收起
展開
球探网即时蓝球比分 pk10免费计划软件赢客 浙江省体彩6+1开奖结果查询 重庆快乐10分任五遗漏 广西快3和值遗漏 青海高频11选5查询 秒速飞艇全部开奖记录 广西快3遗漏值统计表 2019股票配资平台哪个最好 幸运农场是真的吗 内蒙古快3专家的号码了