文章目錄

• 一、指數生成函數求解多重集排列示例

參考博客 : 按照順序看

• 【組合數學】生成函數 簡要介紹 ( 生成函數定義 | 牛頓二項式系數 | 常用的生成函數 | 與常數相關 | 與二項式系數相關 | 與多項式系數相關 )
• 【組合數學】生成函數 ( 線性性質 | 乘積性質 )
• 【組合數學】生成函數 ( 移位性質 )
• 【組合數學】生成函數 ( 求和性質 )
• 【組合數學】生成函數 ( 換元性質 | 求導性質 | 積分性質 )
• 【組合數學】生成函數 ( 性質總結 | 重要的生成函數 ) ★
• 【組合數學】生成函數 ( 生成函數示例 | 給定通項公式求生成函數 | 給定生成函數求通項公式 )
• 【組合數學】生成函數 ( 生成函數應用場景 | 使用生成函數求解遞推方程 )
• 【組合數學】生成函數 ( 使用生成函數求解多重集 r 組合數 )
• 【組合數學】生成函數 ( 使用生成函數求解不定方程解個數 )
• 【組合數學】生成函數 ( 使用生成函數求解不定方程解個數示例 )
• 【組合數學】生成函數 ( 使用生成函數求解不定方程解個數示例 2 | 擴展到整數解 )
• 【組合數學】生成函數 ( 正整數拆分 | 無序 | 有序 | 允許重復 | 不允許重復 | 無序不重復拆分 | 無序重復拆分 )
• 【組合數學】生成函數 ( 正整數拆分 | 無序不重復拆分示例 )
• 【組合數學】生成函數 ( 正整數拆分 | 正整數拆分基本模型 | 有限制條件的無序拆分 )
• 【組合數學】生成函數 ( 正整數拆分 | 重復有序拆分 | 不重復有序拆分 | 重復有序拆分方案數證明 )
• 【組合數學】指數生成函數 ( 指數生成函數概念 | 排列數指數生成函數 = 組合數普通生成函數 | 指數生成函數示例 )
• 【組合數學】指數生成函數 ( 指數生成函數性質 | 指數生成函數求解多重集排列 )

一、指數生成函數求解多重集排列示例

---

使用 $1,2,3,4$ 四個數字組成五位數 , 要求
$1$ 出現次數不能超過 $2$ 次 , 但必須出現 ,
$2$ 出現次數不超過 $1$ 次 ,
$3$ 出現次數最多 $3$ 次 ,
$4$ 出現偶數次 ,
求上述五位數的個數 ;

這就是一個求解 多重集排列 的題目 , 使用 指數生成函數 ;

一共有 $5$ 個位置 , 使用 $1,2,3,4$ 向這 $5$ 個位置中填充 ,

選取個數分析 :

$1$ 出現不超過 $2$ 次 , 不能不出現 , 也就是必須大于 $0$ , 則可選取的個數是 $1,2$ ,

$2$ 出現不超過 $1$ 次 , 可選取個數 $0,1$ ,

$3$ 出現可以達到 $3$ 次 , 可選取的個數 $0,1,2,3$ ,

$4$ 出現偶數次 , 可選取個數是 $0,2,4,6,8,?$ , 這里注意一共選擇 $5$ 個 , 最終求解多重集時 , 主要是看 $x^5$ 前的次冪數 , 因此這里的 可選取個數就是單個因式中的 $x$ 次冪數 , 沒必要超過 $5$ , 選擇 $0,2,4$ 即可 ;

按照下面的模型 , 寫出指數生成函數 ;

多重集 $S=\{n_1?a_1,n_2?a_2,?,n_k?a_k\}$

多重集 $S$ 的 $r$ 排列數 組成數列 $\{a_r\}$ , 對應的指數生成函數是 :

$G_e(x)=f_{n_1}(x)f_{n_2}(x)?f_{n_k}(x)$ ★

其中每個生成函數項 $f_{n_i}(x)$ 是

$f_{n_i}(x)=1+x+\frac{x^2}{2!}+?+\frac{x^{n_i}}{n_i!}$ ★

將 $G_e(x)$ 展開 , 其中的 $r$ 系數就是多重集的排列數 ; ★

指數生成函數寫法 :

① 確定生成函數項個數 : 多重集元素種類個數

② 確定生成函數項中的分項個數 : 選取值 個數 ;

③ 分項格式 : $\frac{x^n}{n!}$

④ 分項次冪 : 選取值 ;

總共有 $4$ 種元素 $1,2,3,4$ , 因此生成函數是 $4$ 個生成函數項相乘 ;

$1$ 元素對應的生成函數項 :

• 選取值 : $1,2$
• 最終結果 : $\frac{x^1}{1!}+\frac{x^2}{2!}=x+\frac{x^2}{2!}$

$2$ 元素對應的生成函數項 :

• 選取值 : $0,1$
• 最終結果 : $\frac{x^0}{0!}+\frac{x^1}{1!}=1+x$

$3$ 元素對應的生成函數項 :

• 選取值 : $0,1,2,3$
• 最終結果 : $\frac{x^0}{0!}+\frac{x^1}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}$

$4$ 元素對應的生成函數項 :

• 選取值 : $0,2,4,6,?$ , 這里只選取 $5$ 個 , 求 $x$ 的次冪的 $5$ 前的系數 , 這里只需要選取到 $0,2,4$ 即可 , $5$ 以上的數完全不需要 , 可以忽略 ;
• 最終結果 : $\frac{x^0}{0!}+\frac{x^2}{2!}+\frac{x^4}{4!}=1+\frac{x^2}{2!}+\frac{x^4}{4!}$

將上述指數生成函數中四個 指數生成函數項相乘 , 計算出 $x^5$ 前的系數 , 就是多重集的排列數 ;

$G_e(x)=(x+\frac{x^2}{2!})(1+x)(1+x+\frac{x^2}{2!}+\frac{x^3}{3!})(1+\frac{x^2}{2!}+\frac{x^4}{4!})$

$=x+5\frac{x^2}{2!}+18\frac{x^3}{3!}+64\frac{x^4}{4!}+215\frac{x^5}{5!}?$

后面的就不算了 , 其中 $x^5$ 的項是 $215\frac{x^5}{5!}$ , 因此題目中要求的 $5$ 位數的個數是 $215$ 個 ;

總結

以上是生活随笔為你收集整理的【组合数学】指数生成函数 ( 指数生成函数求解多重集排列示例 )的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。