文章目錄

• 一、正整數(shù)拆分
• 二、無序拆分
• • 1、無序拆分 不允許重復(fù)
  • 2、無序拆分 允許重復(fù)

參考博客 :

• 【組合數(shù)學(xué)】生成函數(shù) 簡(jiǎn)要介紹 ( 生成函數(shù)定義 | 牛頓二項(xiàng)式系數(shù) | 常用的生成函數(shù) | 與常數(shù)相關(guān) | 與二項(xiàng)式系數(shù)相關(guān) | 與多項(xiàng)式系數(shù)相關(guān) )
• 【組合數(shù)學(xué)】生成函數(shù) ( 線性性質(zhì) | 乘積性質(zhì) )
• 【組合數(shù)學(xué)】生成函數(shù) ( 移位性質(zhì) )
• 【組合數(shù)學(xué)】生成函數(shù) ( 求和性質(zhì) )
• 【組合數(shù)學(xué)】生成函數(shù) ( 換元性質(zhì) | 求導(dǎo)性質(zhì) | 積分性質(zhì) )
• 【組合數(shù)學(xué)】生成函數(shù) ( 性質(zhì)總結(jié) | 重要的生成函數(shù) ) ★
• 【組合數(shù)學(xué)】生成函數(shù) ( 生成函數(shù)示例 | 給定通項(xiàng)公式求生成函數(shù) | 給定生成函數(shù)求通項(xiàng)公式 )
• 【組合數(shù)學(xué)】生成函數(shù) ( 生成函數(shù)應(yīng)用場(chǎng)景 | 使用生成函數(shù)求解遞推方程 )
• 【組合數(shù)學(xué)】生成函數(shù) ( 使用生成函數(shù)求解多重集 r 組合數(shù) )
• 【組合數(shù)學(xué)】生成函數(shù) ( 使用生成函數(shù)求解不定方程解個(gè)數(shù) )
• 【組合數(shù)學(xué)】生成函數(shù) ( 使用生成函數(shù)求解不定方程解個(gè)數(shù)示例 )
• 【組合數(shù)學(xué)】生成函數(shù) ( 使用生成函數(shù)求解不定方程解個(gè)數(shù)示例 2 | 擴(kuò)展到整數(shù)解 )

一、正整數(shù)拆分

---

正整數(shù)拆分 涉及內(nèi)容 :

• 拆分定義與分類
• 無序拆分
• 有序拆分

一個(gè)正整數(shù)可以 拆分成若干正整數(shù) 的和 , 每種不同的拆分方法 , 就可以 看做一個(gè)方案 ;

按照拆分順序進(jìn)行分類 : $4$ 拆分成 $1$ 和 $3$ , $4$ 拆分成 $3$ 和 $1$ ;

• 有序拆分 : 上述 $2$ 個(gè) 正整數(shù)拆分 , 是 兩種不同的拆分方法 ;
• 無序拆分 : 上述 $2$ 個(gè) 正整數(shù)拆分 , 是 同一種拆分方法 ;

按照是否重復(fù)進(jìn)行分類 :

• 允許重復(fù) : 拆分時(shí) , 允許拆分成若干個(gè)重復(fù)的正整數(shù) , 如 $3$ 拆分成 $3$ 個(gè) $1$ ;
• 不允許重復(fù) : 拆分時(shí) , 拆分的正整數(shù) 不允許重復(fù) , 如 $3$ 拆分成 $3$ 個(gè) $1$ 是錯(cuò)誤的 , 只能拆分成 $1,2$ ;

正整數(shù)拆分可以按照性質(zhì) , 分為 $4$ 類 ;

• 有序重復(fù)
• 有序不重復(fù)
• 無序重復(fù)
• 無序不重復(fù)

二、無序拆分

---

無序拆分基本模型 :

將 正整數(shù) $N$ 無序拆分成正整數(shù) , $a_1,a_2,?,a_n$ 是拆分后的 $n$ 個(gè)數(shù) ,

該拆分是無序的 , 上述拆分的 $n$ 個(gè)數(shù)的個(gè)數(shù)可能是不一樣的 ,

假設(shè) $a_1$ 有 $x_1$ 個(gè) , $a_2$ 有 $x_2$ 個(gè) , $?$ , $a_n$ 有 $x_n$ 個(gè) , 那么有如下方程 :

$a_1{x}_1+a_2{x}_2+?+a_n{x}_n=N$

這種形式可以使用 不定方程非負(fù)整數(shù)解個(gè)數(shù) 的生成函數(shù)計(jì)算 , 是 帶系數(shù) , 帶限制條件的情況 , 參考 : 組合數(shù)學(xué)】生成函數(shù) ( 使用生成函數(shù)求解不定方程解個(gè)數(shù) )

無序拆分的情況下 , 拆分后的正整數(shù) , 允許重復(fù) 和 不允許重復(fù) , 是兩類組合問題 ;

如果不允許重復(fù) , 那么這些 $x_i$ 的取值 , 只能 取值 $0,1$ ; 相當(dāng)于 帶限制條件 , 帶系數(shù) 的 不定方程非負(fù)整數(shù)解 的情況 ;

如果 允許重復(fù) , 那么這些 $x_i$ 的取值 , 就是 自然數(shù) ; 相當(dāng)于 帶系數(shù) 的 不定方程非負(fù)整數(shù)解 的情況 ;

1、無序拆分 不允許重復(fù)

討論 無序拆分 , 不允許重復(fù)的情況 , 該方式 等價(jià)于 帶限制條件 , 帶系數(shù) 的 不定方程非負(fù)整數(shù)解 的情況 ;

$a_1$ 項(xiàng)對(duì)應(yīng)的生成函數(shù)項(xiàng) , $x_1$ 取值 $0,1$ , 則對(duì)應(yīng)的生成函數(shù)項(xiàng)是 $(y^{a_1}{)}^0+(y^{a_1}{)}^1=1+y^{a_1}$

$a_2$ 項(xiàng)對(duì)應(yīng)的生成函數(shù)項(xiàng) , $x_2$ 取值 $0,1$ , 則對(duì)應(yīng)的生成函數(shù)項(xiàng)是 $(y^{a_2}{)}^0+(y^{a_2}{)}^1=1+y^{a_2}$

$?$

$a_n$ 項(xiàng)對(duì)應(yīng)的生成函數(shù)項(xiàng) , $x_n$ 取值 $0,1$ , 則對(duì)應(yīng)的生成函數(shù)項(xiàng)是 $(y^{a_n}{)}^0+(y^{a_n}{)}^1=1+y^{a_n}$

將上述生成函數(shù)項(xiàng)相乘 , 則可得到完整生成函數(shù) :

$G(x)=(1+y^{a_1})(1+y^{a_2})?(1+y^{a_n})$

將上述生成函數(shù)寫好之后 , 計(jì)算 展開 , $y$ 的 $N$ 次冪的系數(shù) , 就是 正整數(shù) $N$ 的拆分方案數(shù) ;

2、無序拆分 允許重復(fù)

討論 無序拆分 , 允許重復(fù)的情況 , 該方式 等價(jià)于 不帶限制條件 , 帶系數(shù) 的 不定方程非負(fù)整數(shù)解 的情況 ;

$a_1$ 項(xiàng)對(duì)應(yīng)的生成函數(shù)項(xiàng) , $x_1$ 取值 $0,1,?$ , 則對(duì)應(yīng)的生成函數(shù)項(xiàng)是 $(y^{a_1}{)}^0+(y^{a_1}{)}^1+(y^{a_1}{)}^2=1+y^{a_1}+y^{2a_1}?$

$a_2$ 項(xiàng)對(duì)應(yīng)的生成函數(shù)項(xiàng) , $x_2$ 取值 $0,1,?$ , 則對(duì)應(yīng)的生成函數(shù)項(xiàng)是 $(y^{a_2}{)}^0+(y^{a_2}{)}^1+(y^{a_2}{)}^2=1+y^{a_2}+y^{2a_2}?$

$?$

$a_n$ 項(xiàng)對(duì)應(yīng)的生成函數(shù)項(xiàng) , $x_n$ 取值 $0,1,?$ , 則對(duì)應(yīng)的生成函數(shù)項(xiàng)是 $(y^{a_n}{)}^0+(y^{a_n}{)}^1+(y^{a_n}{)}^2=1+y^{a_n}+y^{2a_n}?$

將上述生成函數(shù)項(xiàng)相乘 , 則可得到完整生成函數(shù) :

$G(x)=(1+y^{a_1}+y^{2a_1}?)(1+y^{a_2}+y^{2a_2}?)?(1+y^{a_n}+y^{2a_n}?)$

上述生成函數(shù)可以根據(jù) 如下生成函數(shù)的常用取值 :

$\{a_n\}$ , $a_n=1^n$ ; $\begin{array}{rl}A(x)& =\sum _{n=0}^{\infty }{x}^n=\frac{1}{1?x}\end{array}$

將 $1+y^{a_1}+y^{2a_1}?$ 中的 $y^{a_1}$ 換元成 $x$ , 則可得到

$1+x+x^2+x^3+?$

對(duì)應(yīng)的數(shù)列是 $1^n$

則上述 $1+y^{a_1}+y^{2a_1}?=\frac{1}{1?y^{a_1}}$

最終化簡(jiǎn)結(jié)果 :

$G(x)=(1+y^{a_1}+y^{2a_1}?)(1+y^{a_2}+y^{2a_2}?)?(1+y^{a_n}+y^{2a_n}?)$

$=\frac{1}{(1?y^{a_1})(1?y^{a_2})?(1?y^{a_n})}$

將上述生成函數(shù)寫好之后 , 計(jì)算 展開 , $y$ 的 $N$ 次冪的系數(shù) , 就是 正整數(shù) $N$ 的拆分方案數(shù) ;

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的【组合数学】生成函数 ( 正整数拆分 | 无序 | 有序 | 允许重复 | 不允许重复 | 无序不重复拆分 | 无序重复拆分 )的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。