排容原理 機率概念與應用網路學習研究.

Presentation on theme: "排容原理 機率概念與應用網路學習研究."— Presentation transcript:

1 排容原理 機率概念與應用網路學習研究

2 「排容原理」是計數原理的第一步，通常我們會直接去求我們所要得到的答案，但如果元素彼此之間有關連的時候，那我們就還得再考慮它們之間的關連有沒有影響到我們得到的答案。

3 試問1至120中，4或6的倍數有幾個？ 4的倍數個數共 個。 6的倍數個數共 個。
4的倍數個數共 個。 6的倍數個數共 個。 將4的倍數個數和6的倍數個數加起來即30+20 = 50個。 此時同時為4及6的倍數之個數算了兩次，因此必須減掉，而在1至120中，同時為4跟6的倍數的數即為12的倍數故共有            個。 因此，4或6的倍數之個數為 =40個。 排容原理

4 若令A為1至120中4的倍數之集合，B為1至120中6的倍數之集合，則 是 12 倍數之集合，   為4或6的倍數之集合，因此                                      。也可用圖形來說明，其中圓A表4的倍數的集合，圓B表6的倍數的集合，而重疊的部分就是12的倍數的集合。 排容原理

5 對任意有限集合 A 及 B， 仍成立，要計算屬於 A 或 B 的元素個數           ，我們先將集合 A 及 B 的元素個數加起來            ，但此時既是 A 也是 B 的元素         ，算了兩次，所以必須減掉，因此得到 。 排容原理

6 參考下圖紅色部分，加了兩次，而藍色部分加了三次，須將重複部分減掉。
對有限集合 A, B, C，我們可用下圖表示，其中圓A、圓B、圓C分別表集合 A, B, C想求屬於集合A, B, C的元素個數|A|+|B|+|C|，先求 參考下圖紅色部分，加了兩次，而藍色部分加了三次，須將重複部分減掉。 排容原理

7 我們將|A|+|B|+|C|減掉 紅色部分被減掉一次，藍色部分卻被減掉三次，因此
沒有包含藍色部分的元素個數，必須再加上去，才是整個圖形的元素個數，即： 排容原理

8 對三個以上的元素，我們也有類似的結果，即對任意有限集合               屬於集合 或 或
或 的元素個數為： 此式可以用數學歸納法證得！ 排容原理

9 另外，如果 為有限集合A的子集合我們亦常會遇到要計算屬於集合A但不屬於集合 的元素個數，
即 ，從    的公式可知，等於： 排容原理

10 假設A為一元素個數的集合，且 為A的n個子集合，則：
排容原理 假設A為一元素個數的集合，且               為A的n個子集合，則： ﹝1﹞ 屬於集合                 的元素個數為： 排容原理

11 假設A為一元素個數的集合，且 為A的n個子集合，則：
排容原理 假設A為一元素個數的集合，且               為A的n個子集合，則： ﹝2﹞ 屬於集合A但不屬於集合 的元素個數為： 排容原理

12 例題1. 求 1～120中，不為4或6的倍數有幾個？ 解答： 我們先算出4或6的倍數個數，根據前面的問題中，可以得知4或6倍數之個數是 =40 (個)，所以算出不為4或6的倍數個數就得120-( )=80(個)。故得知不為4或6倍數之個數為80(個)。 排容原理

13 例題2. 試求1至 1000中不被 2,3,5 整除的個數。 解答： 可以被2整除的個數為500個，可以被3整除的個數為333個，可以被5整除的個數為200個，同時可以被2、3整除的個數為166個，同時能被2、5整除的個數為100個，能同時被3、5整除的個數為66個，同時能被2、3、5整除的個數為33個。所以得到算式為： 1000-( )+( )-33=266 排容原理

14 排容原理是由瑞士人─尤拉(Euler)推展出來的，是一個十分重要的原理，在組合數學領域中使用尤為廣泛、重要。

15 更多的說明，就在 機率網路學習館… 排容原理