作者oyasmy (oyasmy)
看板Math
標題[機統] 排容原理的證明?
時間Thu Jun 26 19:39:04 2025
我認為我已經完成排容原理的證明 但是GTP說我不算完成證明
所以我不確定我是否完成了證明
我要證明的是
n
Σ(-1)^kC(n,k)(n-k)^m=投擲一個n面骰子m次 每一面都至少出現一次的總方法數(式1)
k=0
但是我沒有學過集合論和組合數學 所以WIKI上的證明我看不懂
我只好用土法煉鋼的土炮方法自己證
我的方法是這樣 上面那個Σ式子每經過一個k 它的值就會成為
n
Σ(純j個數字所能構成的方法數)*係數
j=1
以n=5 m=5為例(m不用等於n 我取一樣只是方便)
當k=0 就是+5^5=
+(純1個數字所能構成的方法數)*1+(純2個數字所能構成的方法數)*1
+(純3個數字所能構成的方法數)*1+(純4個數字所能構成的方法數)*1
+(純5個數字所能構成的方法數)*1
然後對於每個給定的n,k,j我們有係數公式:C(n-j,k)(-1)^k
(這個公式的證明後面再補 現在先用)
所以對於上面(式1)的k=0------>n
我們的任一個j 它的係數會是
n-j
ΣC(n-j,k)(-1)^k
k=0
當j=n 上面這個式子的值是1
當1<=j<n 上面這個式子的值是0(二項式展開係數)
(我舉n=5 j=1為例 係數會是+1-4+6-4+1=0)
也就是說 最後只有(純n個數字所能構成的方法數)*1會留下來 其它全歸0
證明完畢 請問我這樣算是完成了證明嗎?
-----
係數公式的證明:
觀察(式1)我們發現k=我們每次操作會缺少的數字的數量
(例如n=5 k=1 (式1)做了-5*4^5 也就是我們這次會一次對4個數字進行操作 而k=5-4=1)
然後我們每次要選取包含那j個數字然後又少k個數字的排列數
那缺少的k個數字 我們是不是只能在剩下的n-j個數字裡面找
所以係數公式:C(n-j,k)(-1)^k
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.61.28.165 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1750937946.A.61A.html
1F：→ R2003 : 你要不要重新回一篇，把證明過程寫清楚? 06/27 06:01
2F：→ R2003 : 不然單靠敘述，沒辦法回答啊 06/27 06:01
3F：→ oyasmy : 啊 那可能要再多花時間 我再想一想 06/27 07:50
4F：→ yhliu : 你這不是在證明排容原理，而是試圖直接證明你原先的 06/30 06:44
5F：→ yhliu : 問題。排容原理是關於 n 個事件聯集機率的一個計算 06/30 06:46
6F：→ yhliu : 式，以 n=2 來說就是 P(A聯B)=P(A)+P(B)-P(AB), 06/30 06:48
7F：→ yhliu : 以 m=3 來說是 P(A聯B聯C) = P(A)+P(B)+P(C)- 06/30 06:49
8F：→ yhliu : P(AB)-P(BC)-P(AC)+P(ABC)。而你原本的問題套用排容 06/30 06:51
9F：→ yhliu : 公式就是 1 - P(至少一面不出現) = 06/30 06:53
10F：→ yhliu : 1 - C(n,1)(1-1/n)^m + C(n,2)(1-2/n)^m - ... 06/30 06:54
11F：→ yhliu : 至於排容原理一般式證明，可以上述 n = 2 情形為基 06/30 06:56
12F：→ yhliu : 楚用數學歸納法進行，或利用指示函數(indicator)。 06/30 06:57