第5章-生成函數(shù)-數(shù)模講座48

Chapter5

生成函數(shù)§1

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

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

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

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

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