文章目錄

• 一、多重集
• 二、多重集全排列
• 三、多重集全排列示例
• 三、多重集非全排列 1 所有元素重復(fù)度大于排列數(shù) ( $n_i\ge r$ )
• 四、多重集非全排列 2 某些元素重復(fù)度小于排列數(shù) ( $n_i\le r$ )

排列組合參考博客 :

• 【組合數(shù)學(xué)】基本計(jì)數(shù)原則 ( 加法原則 | 乘法原則 )
• 【組合數(shù)學(xué)】集合的排列組合問(wèn)題示例 ( 排列 | 組合 | 圓排列 | 二項(xiàng)式定理 )
• 【組合數(shù)學(xué)】排列組合 ( 排列組合內(nèi)容概要 | 選取問(wèn)題 | 集合排列 | 集合組合 )
• 【組合數(shù)學(xué)】排列組合 ( 排列組合示例 )

一、多重集

---

多重集表示 :

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

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

二、多重集全排列

---

多重集 :

$$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!}$$

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

下面是推導(dǎo)過(guò)程

有 $k$ 種元素 ,

放置元素 $a_1$ : 在排列中先放第一種元素 $a_1$ , 該元素有 $n_1$ 個(gè) , $n$ 個(gè)位置中選出 $n_1$ 個(gè) 位置 , 有$C(n,n_1)$ 種方法 ;

$$C(n,n_1)=\frac{n!}{(n?n_1)!n_1!}$$

放置元素 $a_2$ : 放置好 $n_1$ 之后放置第二種元素 $a_2$ , 該元素有 $n_2$ 個(gè) , 此時(shí)還有 $n?n_1$ 個(gè)空位 , 從 $n?1$ 個(gè)位置中選擇 $n_2$ 個(gè)位置有 $C(n?n_1,n_2)$ 種方法 ;

$$C(n?n_1,n_2)=\frac{(n?n_1)!}{(n?n_1?n_2)!n_2!}$$

$$?$$

放置元素 $a_k$ : 放置最后一個(gè)元素 $a_k$ , 該元素有 $n_k$ 個(gè) , 此時(shí)還有 $n?n_1???n_{k?1}$ 個(gè)空位 , 從 $n?n_1???n_{k?1}$ 個(gè)位置中選擇 $n_k$ 個(gè)位置有 $C(n?n_1???n_{k?1},n_k)$ 種方法 ;

$$C(n?n_1???n_{k?1},n_k)=\frac{(n?n_1???n_{k?1})!}{(n?n_1???n_{k?1}?n_k)!n_k!}$$

乘法法則 : 最后根據(jù)乘法法則 , 將上述每個(gè)放置方法乘起來(lái) , 就得到最終的結(jié)果 , 階乘看起來(lái)很復(fù)雜 , 但是 階乘選項(xiàng)如 $(n?n_1???n_{k?1})!$ 都可以約掉 , 最終結(jié)果如下 :

$$\begin{array}{lcl}N& =& C(n,n_1)C(n?n_1,n_2)C(n?n_1???n_{k?1},n_k)\\ & & \\ & =& \frac{n!}{(n?n_1)!n_1!}\times \frac{(n?n_1)!}{(n?n_1?n_2)!n_2!}\times \frac{(n?n_1???n_{k?1})!}{(n?n_1???n_{k?1}?n_k)!n_k!}約掉部分階乘\\ & & \\ & =& \frac{n!}{n_1!n_2!?n_k!}\end{array}$$

三、多重集全排列示例

---

求多重集 $S=\{3?a,2?b,1?c\}$ 的全排列 ?

上述多重集元素總個(gè)數(shù)是 $n=3+2+1=6$ ;

全排列個(gè)數(shù)是 :

$$N=\frac{6!}{3!\times 2!\times 1!}=\frac{6\times 5\times 4\times 3\times 2\times 1}{(3\times 2\times 1)\times (2\times 1)\times (1\times 1)}=60$$

三、多重集非全排列 1 所有元素重復(fù)度大于排列數(shù) ( $n_i\ge r$ )

---

多重集 :

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

★ 非全排列情況 $1$ : $r\le n_i$ , 注意這里的 $r$ 要 小于等于 最小的 $n_i$ ;

$$N=k^r$$

推導(dǎo)過(guò)程 :

在上述條件下 ,

$r$ 個(gè)位置 ,

每個(gè)位置的元素都有 $k$ 種選擇 ,

根據(jù)乘法法則 , 總的選擇個(gè)數(shù)是 $\begin{array}{c}k\times k\times ?\times k\\ r個(gè)k\end{array}$ ,

即 $r^k$ ;

四、多重集非全排列 2 某些元素重復(fù)度小于排列數(shù) ( $n_i\le r$ )

---

上述情況只適用于重復(fù)度足夠大的情況 , 即 每個(gè)元素的重復(fù)度都大于選取個(gè)數(shù) , $r\le n_i$

如果 有一個(gè)元素的重復(fù)度小于選取個(gè)數(shù) , $r\ge n_i$ ,

如 $S=\{3?a,2?b,1?c\}$ 多重集的三排列 , 就無(wú)法使用公式計(jì)算了 ,

沒(méi)有公式可以計(jì)算 , 但是可以 使用 包含排斥原理 , 生成函數(shù) 進(jìn)行計(jì)算 ;

總結(jié)

以上是生活随笔為你收集整理的【组合数学】排列组合 ( 多重集排列 | 多重集全排列 | 多重集非全排列 所有元素重复度大于排列数 | 多重集非全排列 某些元素重复度小于排列数 )的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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