組合數(shù)學(xué) 生成函數(shù)的概念

組合數(shù)學(xué)生成函數(shù)的概念第一頁，共十九頁，編輯于2023年，星期三第2章生成函數(shù)2.1生成函數(shù)的概念2.2生成函數(shù)的運算2.3生成函數(shù)的冪級數(shù)展開式2.4指數(shù)生成函數(shù)2.5生成函數(shù)的應(yīng)用補充第二頁，共十九頁，編輯于2023年，星期三2.1生成函數(shù)的概念2.1.1生成函數(shù)的定義2.1.2相同球分配到不同盒2.1.2重集的組合第三頁，共十九頁，編輯于2023年，星期三2.1.1生成函數(shù)的定義定義2.1.1設(shè)x是一個抽象符號，an(n＝0,1,2,…)為實數(shù)列，若函數(shù)F(x)可表示成F(x)＝a0x0＋a1x1＋a2x2＋…則稱F(x)為數(shù)列an(n＝0,1,2,…)的生成函數(shù)(generatingfunction)。并約定，若某個ai＝0(i＝0,1,2,…)，則項aixi可以略去，且x0可簡記為1。第四頁，共十九頁，編輯于2023年，星期三2.1.1生成函數(shù)的定義數(shù)列,,,…,的生成函數(shù)F(x)＝無窮序列1,1,1,…的生成函數(shù)為F(x)＝x0＋x1＋x2＋x3＋…第五頁，共十九頁，編輯于2023年，星期三

2.1.2相同球分配到不同盒例2.1.1把9個相同球放入5個不同盒中，盒1中只能放奇數(shù)個，盒2中只能放偶數(shù)個，盒3中最少放2個且最多放5個，盒4與5的容量均不限，討論其不同的方案數(shù)a9。第六頁，共十九頁，編輯于2023年，星期三2.1.2相同球分配到不同盒解用xk表示k個球，圓括號表示盒子，做F(x)＝(x1＋x3＋x5＋…)(x0＋x2＋x4＋…)(x2＋x3＋x4＋x5)(x0＋x1＋x2＋x3＋…)(x0＋x1＋x2＋x3＋…)

盒1盒2盒3盒4盒5球的個數(shù)(3)(0)(2)(2)(2)x3

x0

x2

x2

x2＝x9球的個數(shù)(3)(2)(3)(0)(1)x3

x2

x3

x0

x1＝x9題意分配方案F(x)右邊展開式中x9項(未合并同類)a9＝F(x)右邊展開式中x9項的系數(shù)第七頁，共十九頁，編輯于2023年，星期三2.1.2重集的組合例2.1.2設(shè)重集S＝{2·a1,1·a2,∞·a3,9·a4}試討論S的7組合的個數(shù)b7第八頁，共十九頁，編輯于2023年，星期三2.1.2重集的組合解用4個圓括號分別表示a1,a2,a3,a4，做F(x)＝(x0＋x1＋x2)(x0＋x1)(x0＋x1＋x2＋…)(x0＋x1＋x2＋…＋x9){2·a1,2·a3,3·a4}x2

x0

x2

x3＝x7{1·a1,1·a2,4·a3,1·a4}x1

x1

x4

x1＝x7{7·a4}x0

x0

x0

x7＝x7題意分配方案F(x)右邊展開式中x7項(未合并同類)b7＝F(x)右邊展開式中x7項的系數(shù)第九頁，共十九頁，編輯于2023年，星期三2.1.2重集的組合(1)求{a1,a2,…,an}的r組合數(shù)F(x)＝(x0＋x1)n＝(1＋x)n

xr項的系數(shù)(2)求{∞·a1,∞·a2,…,∞·an}的r組合數(shù)F(x)＝(x0＋x1＋x2＋x3＋…)n

xr項的系數(shù)(3)求{t1·a1,t2·a2,…,tn·an}的r組合數(shù)F(x)＝(x0＋x1＋x2＋…＋)…(x0＋x1＋x2＋…＋)(x0＋x1＋x2＋…＋)xr項的系數(shù)第十頁，共十九頁，編輯于2023年，星期三第十一頁，共十九頁，編輯于2023年，星期三第十二頁，共十九頁，編輯于2023年，星期三第十三頁，共十九頁，編輯于2023年，星期三第十四頁，共十九頁，編輯于2023年，星期三第