Tag Archives: 二項式係數

一個關於階乘的恆等式

本文的閱讀等級:初級 這篇短文證明一個關於階乘的恆等式:對於所有的非負整數 和實數 , 。 上式可用於證明:對於任何一個 () 次多項式 , 。 Advertisements

Posted in 特別主題 | Tagged , | Leave a comment

二項式係數與組合問題

本文的閱讀等級:初級 在組合數學,從包含 個元素的集合中選取 個元素的組合數 (不考慮次序),記為 ,稱為二項式係數 (binomial coefficient)。我們先推導 的計算公式。設想有 個人在排隊買電影票,我們可以從 個人中選一人排在第一個位置,再從剩下的 個人裡選一人排在第二個位置,餘此類推,共有 種排列方式。再考慮第二種算法。電影院為鼓勵大眾及早排隊購票,特意準備了 張椅子,,供給排在最前面的 個人歇坐。針對這個情況,從 個人中選取 個人進入歇坐區有 種方式,歇坐區內的 個人有 種排列方式,歇坐區外的 個人有 種排列方式,因此 個人排隊共有 種排列方式。合併上面兩個結果,即得 , 並定義邊界條件 。根據對稱性,。   問題1:你邀請 位好友參加生日宴會,至少有一人出席生日宴會的來賓組合共有多少種? 因為至少有一個人出席派對,出席來賓的組合方式有 。   問題2:投擲一枚公正硬幣 次,出現至少一次正面的機率 (概率) 是多少? 出現 次反面的機率是 ,所以出現至少一次正面的機率是 … Continue reading

Posted in 機率統計 | Tagged , , , | Leave a comment

牛頓的二項式定理 (上)

本文的閱讀等級:初級 公元1676年,萊布尼茲 (Gottfried Wilhelm Leibniz) 向牛頓 (Isaac Newton) 探詢廣義二項式定理的發現過程。6月13日,牛頓透過英國皇家學會 (The Royal Society) 秘書奧登堡 (Henry Oldenberg) 轉寄回函[1]。在這封信中,牛頓寫出下列無窮級數,並稱之為定理[2]: 牛頓解釋 是所考慮的二項式, 是第一項, 是剩餘項除以 ; 可以是整數或分數,為正或負。他舉了一個例子, 對應 , , , [3]。等式右邊的 代表第一項 , 代表第二項 ,餘此類推。換句話說, 。從現代人的眼光來看,牛頓描述的公式顯得深奧晦澀。為甚麼 要出現兩次?何不將 寫成 ?再來,為甚麼不展開等號右邊各項,列出 的顯式表達?原因無他,牛頓的用意在於簡化計算,稍後將說明。我們要討論的第一個問題,也就是萊布尼茲的疑問:牛頓是怎麼得到這條公式的?

Posted in 特別主題, 線性代數專欄 | Tagged , | 5 Comments

遞迴關係式的母函數解法

本文的閱讀等級:初級 美國數學教授維爾夫 (Herbert Wilf) 說[1]:「母函數 (生成函數,generating function) 是一列用來展示一串數字的掛衣架。」母函數是一數列 的一種形式冪級數 (formal power series),其中每一項的係數可以提供關於這個數列的訊息。母函數有多種不同的形式,數列 的普通母函數為 母函數 本身並不是一個從某個定義域映射至某個值域的函數,變數 沒有甚麼特別的意義,取名「函數」僅是出於歷史原因。母函數是一個代數物件而非分析物件,我們只對它的表達形式感興趣,並不關心它是否收斂。母函數經常源自遞迴關係式 (即差分方程)。本文將介紹如何利用母函數方法解出遞迴關係式的代數式。由於我們完全忽略收斂性,母函數方法是否能經得起推敲不免令人生疑。不過母函數至少能夠導出遞迴關係式的猜想,而猜想又可以用數學歸納法來證明。

Posted in 特別主題 | Tagged , , , , , , | Leave a comment

二項式係數公式

本文的閱讀等級:初級 令 表示 個元素構成的集合。從 中選取 個元素的可能方式稱為組合,譬如,從 選取 個元素的組合如下: 。 計算 的 —組合數並不困難:想像 個元素排成一列,選取領先的 個元素,共有 種可能。這 個元素可以任意置換,每一種 —組合重複出現 次。所以,從包含 個元素的集合 中選取 個元素的組合數,記為 ,計算如下: 。 譬如,。我們稱 為二項式係數 (binomial coefficient)。這個名稱的由來係因 , 其中 是 的係數。從二項式係數的表達式可知縱使 不是整數,我們依然能定義 。為便於識別,我們用 代表任一實數, 代表任一整數,定義 。 見下表,非零的部分稱為帕斯卡三角形 (見“特殊矩陣 (15):Pascal 矩陣 … Continue reading

Posted in 特別主題 | Tagged , , , | 1 Comment

特殊矩陣 (15):Pascal 矩陣 (下)

本文的閱讀等級:中級 我們將前文“特殊矩陣 (15):Pascal 矩陣 (上)”的主要結果整理於下。首先定義一 階創造矩陣 :若 ,,否則 。創造矩陣 衍生出矩陣指數,如下: , 其中 是實數。因為 是冪零矩陣,即對於 ,,故 可表示為 的 次多項式: 。 代入 ,可得 ;代入 ,可得 。展開上式等號右邊即推得 的 元:若 , ,否則 。提醒讀者,我們定義 若 , 若 。令帕斯卡矩陣為 (亦即若 ,,否則 ),所以對於任意實數 ,,並有以下必然結果: 。 當 ,即得 … Continue reading

Posted in 特殊矩陣, 線性代數專欄 | Tagged , , , , , , , | 3 Comments

特殊矩陣 (15):Pascal 矩陣 (上)

本文的閱讀等級:中級 二項式定理 (binomial theorem) 由牛頓於公元1664-65年間提出,此定理給出 的整數次冪展開公式: , 其中 為 取 的組合數目,稱為二項式係數,它遵守帕斯卡(Pascal)法則: 。 證明如下。令 表示 個元素構成的集合,設 ,由 中選取 個元素可分開兩種情況討論:若不取 ,則必須從 選取 個元素,組合數為 ;若選取 ,則還要從 取其餘 個元素,組合數為 。帕斯卡法則的代數證明請見“二項式係數公式”。

Posted in 特殊矩陣, 線性代數專欄 | Tagged , , , , , , , , , | 1 Comment