當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

【组合数学】生成函数 ( 正整数拆分 | 正整数拆分基本模型 | 有限制条件的无序拆分 )

發布時間：2025/6/17 编程问答 30 豆豆

生活随笔收集整理的這篇文章主要介紹了【组合数学】生成函数 ( 正整数拆分 | 正整数拆分基本模型 | 有限制条件的无序拆分 ) 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

參考博客 :

無序拆分基本模型 :

將正整數 $N$ 無序拆分成正整數 , $a1,a2,?,ana_1, a_2, \cdots , a_n$ 是拆分后的 $n$ 個數 ,

該拆分是無序的 , 上述拆分的 $n$ 個數的個數可能是不一樣的 ,

假設 $a_1$ 有 $x_1$ 個 , $a_2$ 有 $x_2$ 個 , $?\cdots$ , $a_n$ 有 $x_n$ 個 , 那么有如下方程 :

$a1x1+a2x2+?+anxn=Na_1x_1 + a_2x_2 + \cdots + a_nx_n = N$

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

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

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

對應的生成函數是 : $y^{a_1}) (1+ y^{a_2}) \cdots (1+ y^{a_n})$

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

對應的生成函數是 : $y^{a_1}+ y^{2a_1}\cdots) (1+ y^{a_2} + y^{2a_2}\cdots) \cdots (1+ y^{a_n}+ y^{2a_n}\cdots )$

或 $=\cfrac{1}{ (1-y^{a_1}) (1-y^{a_2}) \cdots (1-y^{a_n}) }$

將正整數 $N$ 無序拆分成正整數 , $a1,a2,?,ana_1, a_2, \cdots , a_n$ 是拆分后的 $n$ 個數 ,

該拆分是無序的 , 上述拆分的 $n$ 個數的個數可能是不一樣的 ,

假設 $a_1$ 有 $x_1$ 個 , $a_2$ 有 $x_2$ 個 , $?\cdots$ , $a_n$ 有 $x_n$ 個 , 那么有如下方程 :

$a1x1+a2x2+?+anxn=Na_1x_1 + a_2x_2 + \cdots + a_nx_n = N$

其中存在限制條件 , $a_i$ 的取值個數 $x_i$ 取值范圍做一下限制 , $li≤xi≤til_i \leq x_i \leq t_i$

上述受限制條件下的無序拆分 , 就是完整的帶系數 , 帶限制條件的不定方程非負整數解的問題 ;

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