文章目錄

• 一、重復有序拆分
• 二、不重復有序拆分
• • 1、無序拆分基本模型
  • 2、全排列
• 三、重復有序拆分方案數證明

參考博客 : 按照順序看

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

一、重復有序拆分

---

將 正整數 $N$ 重復地 , 有序拆分 成 $r$ 部分 , 方案數為 $C(N?1,r?1)$ ★

( 三、中有該組合數由來證明 )

如果對 正整數 $N$ 作 任意重復的有序拆分 , 即可以拆分成 $1$ 個數 , $2$ 個數 , $?$ , $N$ 個數 ,

拆分成 $1$ 個數方案個數是 $\left(\genfrac{}{}{0ex}{}{N?1}{1?1}\right)$

拆分成 $2$ 個數方案個數是 $\left(\genfrac{}{}{0ex}{}{N?1}{2?1}\right)$

$?$

拆分成 $N$ 個數方案個數是 $\left(\genfrac{}{}{0ex}{}{N?1}{N?1}\right)$

上述總的方案個數是 : $\sum _{r=1}^N=2^{N?1}$

( 根據基本組合恒等式計算出來 )

二、不重復有序拆分

---

先進行 不重復無序拆分 , 再進行 全排列 ;

1、無序拆分基本模型

無序拆分基本模型 :

將 正整數 $N$ 無序拆分成正整數 , $a_1,a_2,?,a_n$ 是拆分后的 $n$ 個數 ,

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

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

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

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

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

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

對應的生成函數是 : $G(x)=(1+y^{a_1})(1+y^{a_2})?(1+y^{a_n})$ ★ 重點看這里

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

對應的生成函數是 : $G(x)=(1+y^{a_1}+y^{2a_1}?)(1+y^{a_2}+y^{2a_2}?)?(1+y^{a_n}+y^{2a_n}?)$

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

2、全排列

$n$ 的全排列是 $n!$

$n$ 元集 $S$ , 從 $S$ 集合中選取 $r$ 個元素 ;

根據 元素是否允許重復 , 選取過程是否有序 , 將選取問題分為四個子類型 :

元素不重復元素可以重復

有序選取	集合排列 $P(n,r)$	多重集排列
無序選取	集合組合 $C(n,r)$	多重集組合

選取問題中 :

• 不可重復的元素 , 有序的選取 , 對應 集合的排列 ; $P(n,r)=\frac{n!}{(n?r)!}$
• 不可重復的元素 , 無序的選取 , 對應 集合的組合 ; $C(n,r)=\frac{P(n,r)}{r!}=\frac{n!}{r!(n?r)!}$
• 可重復的元素 , 有序的選取 , 對應 多重集的排列 ; $全排列=\frac{n!}{n_1!n_2!?n_k!}$ , 非全排列 $k^r,r\le n_i$
• 可重復的元素 , 無序的選取 , 對應 多重集的組合 ; $N=C(k+r?1,r)$

三、重復有序拆分方案數證明

---

使用一一對應的方法證明 : 將 正整數 $N$ 重復地 , 有序拆分 成 $r$ 部分 , 方案數為 $C(N?1,r?1)$ ★

拆分后的正整數 , 如果交換了次序之后 , 排列不同 , 其所代表的方案數也不同 ;

將該拆分轉換成組合計數問題 ;

假設 $N=a_1+a_2+?+a_r$ 是滿足條件的拆分 , 該拆分 重復 , 有序 ;

將上述方案 , 做成部分序列 ,

拆分方案 與 拆分序列 :

根據拆分方案寫出拆分序列 :

原始方案 $6=1+2+3$ , 由原始方案作部分序列 ,

第一個序列 $S_1=1$ , 取原始方案的第一個成分 $1$ 出來 ,

第二個序列 $S_2=1+2=3$ , 取原始方案的前兩個成分 $1+2$ 出來 ,

第三個序列 $S_3=1+2+3=6$ , 取原始方案的前三個成分 $1+2+3$ 出來 ,

第一個序列是第一個數 , 第二個序列是前兩個數 , 第 $n$ 個序列是前 $n$ 個數 , 最后一個序列包含了所有的拆分的正整數 ;

只要給定一個原始方案 , 就可以作出上述部分序列出來 ;

只要方案相同 , 作出的序列完全相同 , 方案不同 , 作出的序列肯定不相同 ;

根據拆分序列寫出拆分方案 :

反之 , 給定一個序列 , 可以 還原出一個拆分方案來 , 如給出序列 $S_1=1,S_2=3,S_3=6$ , 對應的拆分方案 :

最后一個序列式所有數之和 , 被拆分的正整數就是最后一個序列的數值 $6$

第一個正整數 就是第一個序列 $1$

第二個正整數 是第二序列減去第一序列 $S_2?S_1=3?1=2$

第三個正整數 是第三序列減去第二序列 $S_3?S_2=6?3=3$

拆分方案是 $6=1+2+3$

$N=a_1+a_2+?+a_r$ 的拆分序列是

$S_1=a_1$

$S_2=a_1+a_2$

$S_3=a_1+a_2+a_3$

$?$

$S_i=a_1+a_2+a_3+?+a_i=\sum _{k=1}^t{a}_i,i=1,2,3,?$

上述的拆分序列一定有下面的性質 :

$0<S_1<S_2<?<S_r=N$

因為 $S_2$ 肯定是 $S_1$ 加上一個正整數 , $S_r$ 肯定是 $S_{r?1}$ 加上一個正整數 , 最后一項是所有的 $r$ 個正整數之和 , 是被拆分的正整數 $N$ ;

上述拆分序列 $S_1,S_2,?,S_r$ , 最后一個數 $S_r=N$ ,

最后一個數不管 , 前面的 $r?1$ 個數的取值范圍是 $1,2,3,?,N?1$ , 上述取值范圍內 有 $n?1$ 個正整數 ;

從 $n?1$ 個正整數中 , 選取 $r?1$ 個正整數 ,

因此, 將 正整數 $N$ 重復地 , 有序拆分 成 $r$ 部分 , 方案數為 $C(N?1,r?1)$ ★

總結

以上是生活随笔為你收集整理的【组合数学】生成函数 ( 正整数拆分 | 重复有序拆分 | 不重复有序拆分 | 重复有序拆分方案数证明 )的全部內容，希望文章能夠幫你解決所遇到的問題。

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