[機統] 排容原理的證明?

[oyasmy (oyasmy)]

我認為我已經完成排容原理的證明 但是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://www.ptt.cc/bbs/Math/M.1750937946.A.61A.html
→ R2003       : 你要不要重新回一篇，把證明過程寫清楚?
→ R2003       : 不然單靠敘述，沒辦法回答啊
→ oyasmy      : 啊 那可能要再多花時間 我再想一想
→ yhliu       : 你這不是在證明排容原理，而是試圖直接證明你原先的
→ yhliu       : 問題。排容原理是關於 n 個事件聯集機率的一個計算
→ yhliu       : 式，以 n=2 來說就是 P(A聯B)=P(A)+P(B)-P(AB),
→ yhliu       : 以 m=3　來說是 P(A聯B聯C) = P(A)+P(B)+P(C)-
→ yhliu       : P(AB)-P(BC)-P(AC)+P(ABC)。而你原本的問題套用排容
→ yhliu       : 公式就是 1 - P(至少一面不出現) =
→ yhliu       : 1 - C(n,1)(1-1/n)^m + C(n,2)(1-2/n)^m - ...
→ yhliu       : 至於排容原理一般式證明，可以上述 n = 2 情形為基
→ yhliu       : 楚用數學歸納法進行，或利用指示函數(indicator)。