排列组合参考博客 :

多重集表示 :

S = { n 1 ⋅ a 1 , n 2 ⋅ a 2 , ⋯   , n k ⋅ a k } ,     0 ≤ n i ≤ + ∞ S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq n_i \leq +\infty S={n1​⋅a1​,n2​⋅a2​,⋯,nk​⋅ak​},   0≤ni​≤+∞

多重集 :

S = { n 1 ⋅ a 1 , n 2 ⋅ a 2 , ⋯   , n k ⋅ a k } ,     0 ≤ n i ≤ + ∞ S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq n_i \leq +\infty S={n1​⋅a1​,n2​⋅a2​,⋯,nk​⋅ak​},   0≤ni​≤+∞

★ 全排列 : r = n 1 + n 2 + ⋯ + n k = n r = n_1 + n_2 + \cdots + n_k = n r=n1​+n2​+⋯+nk​=n

N = n ! n 1 ! n 2 ! ⋯ n k ! N = \cfrac{n!}{n_1! n_2! \cdots n_k!} N=n1​!n2​!⋯nk​!n!​

★ 多重集的全排列数是 元素总数阶乘 , 除以 所有重复度的阶乘 ;

下面是推导过程

有 k k k 种元素 ,

放置元素 a 1 a_1 a1​ : 在排列中先放第一种元素 a 1 a_1 a1​ , 该元素有 n 1 n_1 n1​ 个 , n n n 个位置中选出 n 1 n_1 n1​ 个 位置 , 有 C ( n , n 1 ) C(n, n_1) C(n,n1​) 种方法 ;

C ( n , n 1 ) = n ! ( n − n 1 ) !   n 1 ! C(n, n_1) = \cfrac{n!}{(n-n_1) ! \ n_1!} C(n,n1​)=(n−n1​)! n1​!n!​

放置元素 a 2 a_2 a2​ : 放置好 n 1 n_1 n1​ 之后放置第二种元素 a 2 a_2 a2​ , 该元素有 n 2 n_2 n2​ 个 , 此时还有 n − n 1 n-n_1 n−n1​ 个空位 , 从 n − 1 n-1 n−1 个位置中选择 n 2 n_2 n2​ 个位置有 C ( n − n 1 , n 2 ) C(n-n_1 , n_2) C(n−n1​,n2​) 种方法 ;

C ( n − n 1 , n 2 ) = ( n − n 1 ) ! ( n − n 1 − n 2 ) !   n 2 ! C(n - n_1, n_2) = \cfrac{(n-n_1)!}{(n-n_1 - n_2) ! \ n_2!} C(n−n1​,n2​)=(n−n1​−n2​)! n2​!(n−n1​)!​

⋮ \vdots ⋮

放置元素 a k a_k ak​ : 放置最后一个元素 a k a_k ak​ , 该元素有 n k n_k nk​ 个 , 此时还有 n − n 1 − ⋯ − n k − 1 n-n_1- \cdots -n_{k-1} n−n1​−⋯−nk−1​ 个空位 , 从 n − n 1 − ⋯ − n k − 1 n-n_1- \cdots -n_{k-1} n−n1​−⋯−nk−1​ 个位置中选择 n k n_k nk​ 个位置有 C ( n − n 1 − ⋯ − n k − 1 , n k ) C(n-n_1- \cdots -n_{k-1} , n_k) C(n−n1​−⋯−nk−1​,nk​) 种方法 ;

C ( n − n 1 − ⋯ − n k − 1 , n k ) = ( n − n 1 − ⋯ − n k − 1 ) ! ( n − n 1 − ⋯ − n k − 1 − n k ) !   n k ! C(n-n_1- \cdots -n_{k-1} , n_k) = \cfrac{(n-n_1- \cdots -n_{k-1})!}{(n-n_1- \cdots -n_{k-1} - n_k) ! \ n_k!} C(n−n1​−⋯−nk−1​,nk​)=(n−n1​−⋯−nk−1​−nk​)! nk​!(n−n1​−⋯−nk−1​)!​

乘法法则 : 最后根据乘法法则 , 将上述每个放置方法乘起来 , 就得到最终的结果 , 阶乘看起来很复杂 , 但是 阶乘选项如 ( n − n 1 − ⋯ − n k − 1 ) ! (n-n_1- \cdots -n_{k-1})! (n−n1​−⋯−nk−1​)! 都可以约掉 , 最终结果如下 :

N = C ( n , n 1 ) C ( n − n 1 , n 2 ) C ( n − n 1 − ⋯ − n k − 1 , n k ) = n ! ( n − n 1 ) !   n 1 ! × ( n − n 1 ) ! ( n − n 1 − n 2 ) !   n 2 ! × ( n − n 1 − ⋯ − n k − 1 ) ! ( n − n 1 − ⋯ − n k − 1 − n k ) !   n k !     约 掉 部 分 阶 乘 = n ! n 1 ! n 2 ! ⋯ n k ! \begin{array}{lcl} N & = & C(n, n_1) C(n - n_1, n_2) C(n-n_1- \cdots -n_{k-1} , n_k) \\\\ & = & \cfrac{n!}{(n-n_1) ! \ n_1!} \times \cfrac{(n-n_1)!} {(n-n_1 - n_2) ! \ n_2!} \times \cfrac{(n-n_1- \cdots -n_{k-1})!}{(n-n_1- \cdots -n_{k-1} - n_k) ! \ n_k!} \ \ \ 约掉部分阶乘 \\\\ &=& \cfrac{n!}{n_1! n_2! \cdots n_k!} \end{array} N​===​C(n,n1​)C(n−n1​,n2​)C(n−n1​−⋯−nk−1​,nk​)(n−n1​)! n1​!n!​×(n−n1​−n2​)! n2​!(n−n1​)!​×(n−n1​−⋯−nk−1​−nk​)! nk​!(n−n1​−⋯−nk−1​)!​   约掉部分阶乘n1​!n2​!⋯nk​!n!​​

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

上述多重集元素总个数是 n = 3 + 2 + 1 = 6 n = 3 + 2 + 1 = 6 n=3+2+1=6 ;

全排列个数是 :

N = 6 ! 3 ! × 2 ! × 1 ! = 6 × 5 × 4 × 3 × 2 × 1 ( 3 × 2 × 1 ) × ( 2 × 1 ) × ( 1 × 1 ) = 60 N = \cfrac{6!}{3! \times 2! \times 1!} = \cfrac{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 N=3!×2!×1!6!​=(3×2×1)×(2×1)×(1×1)6×5×4×3×2×1​=60

多重集 :

S = { n 1 ⋅ a 1 , n 2 ⋅ a 2 , ⋯   , n k ⋅ a k } ,     0 ≤ n i ≤ + ∞ S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq n_i \leq +\infty S={n1​⋅a1​,n2​⋅a2​,⋯,nk​⋅ak​},   0≤ni​≤+∞

★ 非全排列情况 1 1 1 : r ≤ n i r \leq n_i r≤ni​ , 注意这里的 r r r 要 小于等于 最小的 n i n_i ni​ ;

N = k r N = k^r N=kr

推导过程 :

在上述条件下 ,

r r r 个位置 ,

每个位置的元素都有 k k k 种选择 ,

根据乘法法则 , 总的选择个数是 k × k × ⋯ × k ⏟ r 个 k \begin{matrix} \underbrace{ k \times k \times \cdots \times k } \\ r 个 k \end{matrix} k×k×⋯×k​r个k​ ,

即 r k r^k rk ;

上述情况只适用于重复度足够大的情况 , 即 每个元素的重复度都大于选取个数 , r ≤ n i r \leq n_i r≤ni​

如果 有一个元素的重复度小于选取个数 , r ≥ n i r \geq n_i r≥ni​ ,

如 S = { 3 ⋅ a , 2 ⋅ b , 1 ⋅ c } S=\{ 3 \cdot a , 2 \cdot b , 1 \cdot c \} S={3⋅a,2⋅b,1⋅c} 多重集的三排列 , 就无法使用公式计算了 ,

没有公式可以计算 , 但是可以 使用 包含排斥原理 , 生成函数 进行计算 ;