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

[oyasmy (oyasmy)]

因為上一篇像是講故事不像是證明
有熱心板友建議我再發一篇證明
我發現把想法轉譯成數學語言真的很困難
也更加敬佩板上那些很會寫證明文的高手

證明目標:投擲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
→ R2003       : A(n,m,j)是甚麼東西?
→ R2003       : Σ(j=1 n)Σ(k=0 n-j) C(n-j,k)(-1)^k*A(n,m,j)
→ R2003       : = =A(n,m,n)
→ R2003       : 這是怎麼來的?
→ R2003       : 因為你有對A(n,m,j)進行操作，所以要寫出這有甚麼
→ R2003       : 數學意涵
啊抱歉我沒有寫得很清楚
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
→ R2003       : 強烈不建議把那麼多non-trivial的東西放在QED之後
→ R2003       : 建議你的補充說明1、2要放在 "原式=(下略)" 之前
→ R2003       : 然後嚴謹的證明裡不應出現"先用，等等再證"這件事
→ R2003       : 另外，有時候證明不要省略太多敘述
→ R2003       : 如果省略的部分太trivial或是可以用定理總結
→ R2003       : 我個人除了直接放"="外，還是會加上
→ R2003       : and by xxx thm, we got ....
→ R2003       : 像你後來回覆的部分，我就會提示跟二項式定理有關
→ oyasmy      : 感謝提醒 學到了很多 謝謝~