天天看點

母函數簡介

母函數簡介

根據定義,這個序列作為函數的系數,稱G(x)就是序列的母函數。和一般意義上的函數相比,母函數的功能是計數。

從百度和維基上能找到的相關說明都顯得太學院派,不容易了解,還是用例子說明并引入吧。

有這樣一道例題:

母函數簡介

到這一章為止,已知的計數法則就兩種,加法法則(或)和乘法法則(且)。前者是分類思想,後者是分步。

法1:分步來看,第一個骰子有1-5種可能,因為兩個骰子之和是6,是以一旦第一個骰子确定了,第二個骰子也就随之确定。第一個骰子的每一種可能性都僅對應第二個骰子的唯一确定的點數。是以5*1=5種。

法2:分類來看,有可能是1+5=5+1或2+4=4+2或3+3=3+3,累加起來,一共五種可能。

當然這個是最最簡單的例子,也很容易想,但如果骰子有很多呢?

母函數簡介

這種情況下,挨個挨個地枚舉顯然是愚蠢的。而伯努利在300年前已經研究過這個問題了,是關于“投擲m粒骰子時,點數總和為n的可能方案數”,這個問題乍看之下很複雜,令人懷疑人生。

那麼先從簡單情形考慮,兩個骰子擲出n點,有多少種可能。這相當于把n拆分成兩個數的和,這時候對n枚舉就很複雜,是以對兩個骰子枚舉。第一個骰子,6種可能,互相之間是“或”的關系,對應的是加法,但是不能直接相加,因為這無法反映兩個骰子的疊加過程。

我們需要逐個分析一個骰子的不同情況,對于一個骰子,假如擲出2個點,就可以看作一個分步政策,相當于——先擲一個點,再擲一個點,是以是(●)^2,當然這樣不習慣,于是用x^2來表示。那四個點是x^4,是以可以用指數對應點數。

這樣就可以用(x+x^2+…+x^6)表示一個骰子的投擲過程,對于第二個骰子也是這樣,最後兩式相乘,x^6前面的系數就是有多少種出現6點的方案。

母函數簡介

最後的母函數求出來是

母函數簡介
母函數簡介

兩個骰子擲出n點的可能方法數就是求G(x)中x^n的系數。實際上系數起了關鍵性的作用,母函數中的系數對應了計數序列。

那麼回溯到最初伯努利提出的問題,m粒骰子就是m個多項式累乘

母函數簡介

而要求點數總和為n的可能方案數,也就是求展開式中x^n的系數。這可以看出來,對于這個多項式,我們并不關心它的值,現在關心的卻是它的系數了。(是以母函數确實是一位母親,計數序列作為系數就是她的孩子233)

是以母函數的定義我們可以進一步提煉出兩點

  1. 關注每一個計數的序列
  2. 每一個計數序列對應的是x^n

而這個定義是拉普拉斯在研究機率的時候,研究了母函數的方法和相關定義。(1812年拉普拉斯在著作《機率的分析理論》第一卷中系統地研究了母函數的方法和有關理論)

最後總結一下,母函數實際上是用來做什麼的,以及它和函數有什麼差別。

對于母函數

      • 是計數工具,x的取值我們不關心,似乎隻是個占位置的東西
      • 不考慮斂散性
      • 不考慮實際上的函數值
      • 形式幂級數(Formal power series)

雖然形式上是函數,但“似函數,非函數”。

那——為什麼要引入一個母函數呢?因為在現實世界裡,對于各種複雜的事件,我們要通過“映射”的方式将其簡化,比如說對于分數幂的運算十分困難,我們用一個對數映射将其簡化,再求原問題的解,就相對容易了。

母函數簡介

在母函數中同樣如此,在一開始思考的骰子問題裡,直接計算是十分困難的,後來發現通過分步來考慮的時候,把多項式引入,求出相應系數後再對應回來,就得到了解。

母函數簡介

其實母函數蘊含的就是一種映射關系。

那麼是什麼原因使得母函數具備了計數的法則呢,在骰子那道題中,通過求系數來對應方案數是一個例子。分析一下,對于一般的多項式,可以寫成

母函數簡介

這種形式,展開後的某個幂次的系數可以分為兩部分,分别來自于兩個括号裡的某一項,這實際上就是對應的乘法法則

母函數簡介

 是以實質上是多項式的乘法運算使母函數具有了計數能力。

“母函數就是一列用來展示一串數字序列的挂衣架”

——赫伯特·維爾夫

繼續閱讀