Re: [機統] 排容原理的證明?
因為上一篇像是講故事不像是證明
有熱心板友建議我再發一篇證明
我發現把想法轉譯成數學語言真的很困難
也更加敬佩板上那些很會寫證明文的高手
證明目標:投擲n面骰子一個m次 每個面都至少出現一次的排列數為
Σ(k=0 to n)(-1)^k*C(n,k)(n-k)^m(原式)
令A(n,m,j)代表恰好使用j種點數的排列總數
其中(-1)^k*C(n,k)(n-k)^m=Σ(j=1 to n-k)C(n-j,k)(-1)^k*A(n,m,j)
(這個等式後面再證明 現在先用)
原式=Σ(k=0 to n)(-1)^k*C(n,k)(n-k)^m=Σ(k=0 to n)Σ(j=1 to
n-k)C(n-j,k)(-1)^k*A(n,m,j)=Σ(j=1 to n)Σ(k=0 to
n-j)C(n-j,k)(-1)^k*A(n,m,j)=A(n,m,n)
也就是只剩下"恰好使用n種點數的排列總數"會保留下來
證明完成#
不知道這個證明是否算是一個完整有效的證明?
如果有錯誤或不足還請板上高手不吝指教
-----
補充說明
1.Σ(k=0 to n-j)C(n-j,k)(-1)^k展開就會變成(1-1)^(n-j)=0(當j<n)
2.(-1)^k*C(n,k)(n-k)^m=Σ(j=1 to n-k)C(n-j,k)(-1)^k*A(n,m,j)的證明
這個等式雖然直覺可以想到 但是我不知道怎麼證明(要證明它比想到它要困難很多)
所以我學習了一種叫"雙重計數法"的知識
首先 左右邊的(-1)^k都拿掉 我們就只要證明
C(n,k)(n-k)^m=Σ(j=1 to n-k)C(n-j,k)A(n,m,j)
我們要數的東西是 一個配對(K,P)的數量
其中
K=一個恰好包含k個點數的集合 我們稱為"禁止出現組"
P=一個避開"禁止出現組" 且長度為m的排列
先看等式左邊 先選K 從n中選取k的方法為C(n,k)
再選P 從剩下的n-k個點數中 選取長度為m的排列數為(n-k)^m
所以(K,P)的數量=C(n,k)(n-k)^m
再看等式右邊 我們這次先選P 再選K
A(n,m,j)代表恰好使用j種點數的排列總數 對於這樣一個P 它可以跟多少個K
進行配對呢?答案當然是C(n-j,k) (K,P)的數量就是我們把它們全部加起來
Σ(j=1 to n-k)C(n-j,k)A(n,m,j)
j的範圍可以從1到n-k(因為P至少要留下k個空位給K）
因為左右二邊數的都是一樣的數字(K,P) 所以左右二邊相等
得證
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.61.28.165 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1751087105.A.950.html
→
06/28 14:12,
6月前
, 1F
06/28 14:12, 1F
→
06/28 14:14,
6月前
, 2F
06/28 14:14, 2F
→
06/28 14:15,
6月前
, 3F
06/28 14:15, 3F
→
06/28 14:15,
6月前
, 4F
06/28 14:15, 4F
→
06/28 14:19,
6月前
, 5F
06/28 14:19, 5F
→
06/28 14:19,
6月前
, 6F
06/28 14:19, 6F
啊抱歉我沒有寫得很清楚
A(n,m,j) 代表的是：「投擲n面骰m次，其排列結果中，『恰好』只出現 j 種不同數字」
的方法總數。
例如:A(5,5,4) 是投擲一個5面骰子5次 所有恰好出現4種數字的排列總數
（例如 1,1,2,3,4 這種）。
A(5,5,1) 是所有只出現1種數字的排列總數（例如 1,1,1,1,1，總共有5種）
至於Σ(j=1 to n)Σ(k=0 to n-j)C(n-j,k)(-1)^k*A(n,m,j)=A(n,m,n)
假設我們n=5 m=5 外層j=1 那麼內層就是Σ(k=0 to 4)C(4,k)(-1)^k*A(5,5,1)
=(1-4+6-4+1)A(5,5,1)=0
事實上 因為二項式定理 對於所有的1<=j<n 內層的求和式Σ(k=0 to
n-j) C(n-j,k)(-1)^k 就等於(1-1)^(n-j) 結果永遠是0
只有當外層的j=n的時候
內層Σ(k=0 to n-n)C(0,k)(-1)^k*A(n,m,n)=C(0,0)(-1)^0*A(n,m,n)=A(n,m,n)
希望這樣的解釋有比較清楚 感謝R大的提醒 我之前寫得太簡略了
※ 編輯: oyasmy (61.61.28.165 臺灣), 06/28/2025 17:19:17
→
06/28 20:24,
6月前
, 7F
06/28 20:24, 7F
→
06/28 20:26,
6月前
, 8F
06/28 20:26, 8F
→
06/28 20:28,
6月前
, 9F
06/28 20:28, 9F
→
06/28 20:30,
6月前
, 10F
06/28 20:30, 10F
→
06/28 20:31,
6月前
, 11F
06/28 20:31, 11F
→
06/28 20:31,
6月前
, 12F
06/28 20:31, 12F
→
06/28 20:32,
6月前
, 13F
06/28 20:32, 13F
→
06/28 20:34,
6月前
, 14F
06/28 20:34, 14F
→
06/28 21:06,
6月前
, 15F
06/28 21:06, 15F
討論串 (同標題文章)