文章目錄

• 一、多重集組合 ( 所有元素重復度大于組合數 )
• 二、多重集組合 所有元素重復度大于組合數 推導 1 ( 分割線推導 )
• 二、多重集組合 所有元素重復度大于組合數 推導 2 ( 不定方程非負整數解個數推導 )

排列組合參考博客 :

• 【組合數學】基本計數原則 ( 加法原則 | 乘法原則 )
• 【組合數學】集合的排列組合問題示例 ( 排列 | 組合 | 圓排列 | 二項式定理 )
• 【組合數學】排列組合 ( 排列組合內容概要 | 選取問題 | 集合排列 | 集合組合 )
• 【組合數學】排列組合 ( 排列組合示例 )
• 【組合數學】排列組合 ( 多重集排列 | 多重集全排列 | 多重集非全排列 所有元素重復度大于排列數 | 多重集非全排列 某些元素重復度小于排列數 )

一、多重集組合 ( 所有元素重復度大于組合數 )

---

多重集 :

$$S=\{n_1?a_1,n_2?a_2,?,n_k?a_k\},0\le n_i\le +\infty$$

• 元素種類 : 多重集中含有 $k$ 種不同的元素 ,
• 元素表示 : 每個元素表示為 $a_1,a_2,?,a_k$ ,
• 元素個數 : 每個元素出現的次數是 $n_1,n_2,?,n_k$ ,
• 元素個數取值 : $n_i$ 的取值要求是 大于 $0$ , 小于正無窮 $+\infty$ ;

上述多重集的組合 , 當 所有元素的重復度 $n_i$ 組大于組合數 $r$ 時 , $r\le n_i$ 時 , 多重集的組合數為

$$N=C(k+r?1,r)$$

二、多重集組合 所有元素重復度大于組合數 推導 1 ( 分割線推導 )

---

多重集 :

$$S=\{n_1?a_1,n_2?a_2,?,n_k?a_k\},0\le n_i\le +\infty$$

取 $r$ 種元素的組合 , $r\le n_i$ , 推導過程如下 :

在 $k$ 種元素中 , 取 $r$ 種元素 , 每種元素取 $0～r$ 個不等的元素 ,

使用 $k?1$ 個分割線分割 $k$ 種元素的位置 , $k?1$ 個分割線相當于組成了 $k$ 個盒子 , 在每個盒子中放 $0～r$ 個不等的元素 ,

放置的總元素的個數是 $r$ 個 , 分割線個數是 $k?1$ 個 , 這里就產生了一個組合問題 , 在 $k?1$ 個分割線 和 $r$ 個元素之間 , 選取 $r$ 個元素 , 就是 多重集的 $r\le n_i$ 情況下的 組合個數 ;

結果是 :

$$N=C(k+r?1,r)$$

二、多重集組合 所有元素重復度大于組合數 推導 2 ( 不定方程非負整數解個數推導 )

---

多重集 :

$$S=\{n_1?a_1,n_2?a_2,?,n_k?a_k\},0\le n_i\le +\infty$$

取 $r$ 種元素的組合 , $r\le n_i$ , 推導過程如下 :

多重集 $S$ 每個元素取值 :

• 第 $1$ 種元素取值個數 : 元素 $a_1$ 的取值個數是 $x_1$ ,

• 第 $2$ 種元素取值個數 : 元素 $a_2$ 的取值個數是 $x_2$ ,

$?$

• 第 $k$ 種元素取值個數 :元素 $a_k$ 的取值個數是 $x_k$ ;

不定方程 $x_1+x_2+?+x_k=r$ ;

$x_i$ 可以為 $0$ , 即某個元素取值個數可以是 $0$ ;

則多重集 $S$ 的 $r$ 組合是 : $$\{x_1?a_1,x_2?a_2,?,x_k?a_k\}$$

$x_i$ 的取值是非負整數

多重集組合與方程對應 : 只要有一個 $r$ 組合 , 就可以寫出一個對象的 方程 $x_1+x_2+?+x_k=r$ 出來 ;

非負整數解與多重集組合對應 : $x_1+x_2+?+x_k=r$ 不定方程的一組非負整數解 , 就對應著 一個 $S$ 多重集的 $r$ 組合 ;

一一對應關系 : 上述

方程的非負整數解的個數

與

$S$ 多重集的 $r$ 組合個數 一一對應 ;

求 $S$ 多重集的 $r$ 組合數 , 就可以轉化成 求 $x_1+x_2+?+x_k=r$ 方程非負整數解個數 ;

將上述解寫成一個序列 , 序列中使用 $k?1$ 個 $0$ , 分割 $k$ 組 $1$ ;

$\begin{array}{c}1?1\\ x_1個1\end{array}$ $0$ $\begin{array}{c}1?1\\ x_2個1\end{array}$ $0$ $\begin{array}{c}1?1\\ x_3個1\end{array}$ $0$ $?$ $0$ $\begin{array}{c}1?1\\ x_k個1\end{array}$

不定方程每個解 都對應著 上述 $k?1$ 個 $0$ 和 $r$ 個 $1$ 的一個排列 ;

相當于一個多重集 $S^{\prime }=\{r?1,(k?1)?0\}$ 的全排列 ;

這里就將 多重集的組合問題 , 轉化成了 另外一個多重集的全排列問題 , 多重集全排列是有公式的 ;

多重集全排列的公式是 : ( 回顧知識點 ① )

$$S=\{n_1?a_1,n_2?a_2,?,n_k?a_k\},0\le n_i\le +\infty$$

★ 全排列 : $r=n_1+n_2+?+n_k=n$

$$N=\frac{n!}{n_1!n_2!?n_k!}$$

★ 多重集的全排列數是 元素總數階乘 , 除以 所有重復度的階乘 ;

參考 : 【組合數學】排列組合 ( 多重集排列 | 多重集全排列 | 多重集非全排列 所有元素重復度大于排列數 | 多重集非全排列 某些元素重復度小于排列數 ) 二、多重集全排列

( 回顧知識點完畢 ① )

可以根據上述公式 , 計算 多重集 $S^{\prime }=\{r?1,(k?1)?0\}$ 的全排列 , 結果是 :

$$N=\frac{(r+k?1)!}{r!(k?1)!}$$

★ 排列數與組合數回顧 : ( 回顧知識點 ② )

• 排列數 : $n$ 元集 $S$ , 從 $S$ 集合中 有序 , 不重復 選取 $r$ 個元素 , $P(n,r)=\frac{n!}{(n?r)!}$
• 組合數 : $n$ 元集 $S$ , 從 $S$ 集合中 無序 , 不重復 選取 $r$ 個元素 , $C(n,r)=\frac{P(n,r)}{r!}\frac{n!}{(n?r)!r!}$

參考 : 【組合數學】排列組合 ( 排列組合內容概要 | 選取問題 | 集合排列 | 集合組合 )

( 回顧知識點完畢 ② )

由上述的組合數可以看出 , $$N=\frac{(r+k?1)!}{r!(k?1)!}$$

的值正好是從 $r+k?1$ 個元素中取 $r$ 個元素的組合數 ;

$$N=\frac{(r+k?1)!}{r!(k?1)!}=C(r+k?1,r)$$

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

總結

以上是生活随笔為你收集整理的【组合数学】排列组合 ( 多重集组合数 | 所有元素重复度大于组合数 | 多重集组合数 推导 1 分割线推导 | 多重集组合数 推导 2 不定方程非负整数解个数推导 )的全部內容，希望文章能夠幫你解決所遇到的問題。

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