2013年10月12日 星期六

樂透恆等式

剛剛閒閒沒事在翻我以前寫的這篇 大樂透各獎項中獎機率分析
這篇原本是寫在無名的,後來搬到Blogger這裡來
其實我每次打開無名都會先看到這篇文章,因為這是我在無名上寫的最後一篇文章,後來就搬家了
雖然看到這篇N次了,但我一直沒有發現,這篇內容可以當巴斯卡定理的推廣啊啊啊啊啊
後來發現,其實Vandermonde's identity比較接近這定理
因為不知道有沒有人發現過這玩意,所以我暫時叫它「樂透恆等式」好了XD

$\text{Theorem: (Lottery equality) Let }n=n_1+n_2+\cdots+n_k\text{. Then}$\[
{n \choose m} = \sum_{0\leq m_i\leq n_i\atop m_1+m_2+\cdots m_k=m}{n_1 \choose m_1}{n_2 \choose m_2}\cdots{n_k \choose m_k}.
\]
##ReadMore##

取$n_1=n-1,\ n_2=1$,就是巴斯卡定理:
\begin{align*}
{n \choose m} &= {n-1 \choose m}{1 \choose 0}+{n-1 \choose m-1}{1 \choose 1}\\
&= {n-1 \choose m}+{n-1 \choose m-1}
\end{align*}

大樂透的所有組合數就是取$n_1=6,\ n_2=1,\ n_3=42$,其中$n_1=6$代表6個一般號,$n_2=1$代表1個特別號,$n_3=42$代表剩下42個不會中獎的號碼

常見的\[{2n \choose n} = \sum_{k=0}^n {n \choose k}{n \choose n-k}\]也可以用這個定理直接推論

證明我就懶得證了,反正應該是用數學歸納法之類的吧XD
不過今天和同學討論,發現一個很直觀的證明
假設現在要從$n$個人裡面挑$m$個人,那我們可以把這$n$個人拆成$k$堆,即$n=n_1+n_2+\cdots+n_k$。從$n_1,\ n_2,\ \ldots,\ n_k$這$k$堆人裡面分別挑$m_1,\ m_2,\ \ldots,\ m_k$人,可以有${n_1 \choose m_1}{n_2 \choose m_2}\cdots{n_k \choose m_k}$種挑法,其中$m_1+m_2+\cdots m_k=m$。把所有的挑法全部加起來就是等式右邊了。