Chapter5

生成函數§1

生成函數簡介一.定義1.例1：a,b,c三個球，現從中選球：取1個球：a+b+c取2個球：ab+bc+ca取3個球：abc多項式表示：(1+ax)(1+bx)(1+cx)=1+(a+b+c)x+(ab+bc+ca)x2+(abc)x3注：(1)xk的系數為從三個數中選取k個的方法之形象表示

(2)(1+ax)可表為對球a或不選或選例2.兩個色子擲出6點，有多少種擲法？把色子出現的點數1,2,…6和t,…,t6對應起來這種對應把組合問題的加法法則和冪級數的t的乘冪的相加對應起來。故使兩個色子擲出6點的方法數等價于求生成函數的思想—把離散數列和冪級數一一對應起來，把離散數列間的相互結合關系對應成為冪級數間的運算關系，最后由冪級數形式來確定離散數列的構造.進一步：10個色子擲出30點，有多少種擲法？注：(1)數列可有限可無限(2)只是形式冪級數(3)x可換做別的g(x)，只是標志函數二.數列與冪級數的運算2.代數運算：3.分析運算：4.柯西乘積：注：(1)稱{cn}為數列{an}與{bn}的柯西乘積，記為{cn}={an}*{bn}(2)此即冪級數運算中的乘法部分三.幾個常見數列的生成函數四.應用1.應用之一：組合恒等式的證明2.應用之二：求數列的前n項之和(n≥0)3.應用之三：求解遞推關系4.應用之四：計算重復組合數一.定義1.問題：考慮如下不定方程(*)的非負整數解的個數：x1+…+xk=n,xi∈Si,(i=1,…,k)

注：此即從k種不同的元素中重復取n個，使得第i個元所取個數∈Si(i=1,…,k)的個數

注：當k個子集Si取定時，此即一個數列{cn}注：(1).此即用生成函數去求解重復組合數(2).思路：第一步：根據限制集Si求出生成函數第二步：展開成冪級數第三步：求出系數an即得二.實例解：此即所有Si為非負整數集合N0例2：從一堆水果中選出n個，使得蘋果數為偶數，香蕉數為5的倍數，桔子數不超過4個(可為4)，梨子數或0或1，求選出n個的選法數.故：an=n+1.例3:任一正整數n，均可表示為的形式，且表示法唯一.一.思考：為何會利用指母函數？2.現排列數P(n,k)在上述形式下不易化簡！但P(n,k)=C(n,k)k!，故而：§2指數型生成函數二.幾個常見數列的指母函數：三.應用指母函數求解重復排列問題注：(1)證明中先將重復度固定3：定理3：(2)帶限制條件的重復排列可由此解決五.實例解：此即所有Si=N0的情況解：此即Si={0,1,...,ni},i=1,2,...,k的情況例4:

求1，3，5，7，9五個數字組成的n位數的個數an，要求其中3，7出現的次數為偶數，其他1，5，9出現次數不加限制.§3分配問題一.簡介1.問題：將n個球放到r個盒中的放法問題2.考慮因素：(1).球是否相同(2).盒子是否相同(3).是否允許有空盒(4).不考慮球在盒子內部的順序(5).不限制盒子的容量二.情況討論Proof：此即n元集的無序r劃分Proof：分類，設有i個非空盒子即可Proof：先設盒子相同，再對盒子排列即可Proof：每個球有r種選擇注：(1)此即n元集X到r元集Y的映射的個數附錄：Stirling數簡介1.兩組多項式的互相表出：{(x)0,(x)1,…,(x)n}與{x0,x1,…,xn}注:(1)s(i,j)即稱為第一類Stirling數(2)易見：s(n,0)=0,(n≥1);s(n,n)=12.反之：注:(1)S(i,j)即稱為第二類Stirling數(2)易見：S(n,0)=0,(n≥1);S(n,n)=13.矩陣表示注:(1)此兩類Stirling數均與x無關(2)兩類矩陣均為對角元全1的下三角陣(3)