【DM】多重集合组合

组合"/>

【DM】多重集合组合

• 多重集的 r r r 组合是指从集合中无序地选出 r r r 个元素。 r r r 组合自身也是一个多重集，例如我们给定多重集： M = { 4 ⋅ a , 2 ⋅ b , 3 ⋅ c } M=\{4\cdot a,2\cdot b,3\cdot c\} M={4⋅a,2⋅b,3⋅c}那么该多重集的 2 2 2 组合会包括诸如 { a , a } , { b , b } , { c , c } \{a,a\},\{b,b\},\{c,c\} {a,a},{b,b},{c,c} 这样的多重集。

• 【定理】给定多重集 M = { ∞ ⋅ a 1 , ∞ ⋅ a 2 , ⋯ , ∞ ⋅ a k } M=\{\infin\cdot a_1,\infin\cdot a_2,\cdots,\infin\cdot a_k\} M={∞⋅a1​,∞⋅a2​,⋯,∞⋅ak​}，其 r r r 组合的数量为： ( k − 1 + r r ) \binom{k-1+r}{r} (rk−1+r​)
• 【证明.1】不难发现， r r r 组合本质上可以视为多重集 M M M 的一个 r r r 元子集，设其 r r r 组合为： { x 1 ⋅ a 1 , x 2 ⋅ a 2 , ⋯ , x k ⋅ a k } \{x_1\cdot a_1,x_2\cdot a_2,\cdots,x_k\cdot a_k\} {x1​⋅a1​,x2​⋅a2​,⋯,xk​⋅ak​}其中重数满足： x 1 + x 2 + ⋯ + x k = r (*) x_1+x_2+\cdots+x_k=r\tag{*} x1​+x2​+⋯+xk​=r(*)那么上述求取多重集 r r r 组合数量的问题就转换为求解 ( ∗ ) (*) (∗) 式中 { x i ∣ i = 1 , 2 , ⋯ , k } \{x_i|i=1,2,\cdots,k\} {xi​∣i=1,2,⋯,k} 有多少组非负整数解，非负整数解与 r r r 组合之间的映射关系是双射函数。
• 一种极为巧妙的方法是，我们将一组非负整数解表示为如下的 0 , 1 0,1 0,1 序列： 11111 ⋯ 11 ⏞ x 1 0 1111 ⋯ 11 ⏞ x 2 0 ⋯ 0 111 ⋯ 11 ⏞ x k (1) \overbrace{11111\cdots11}^{x_1}~0~\overbrace{1111\cdots11}^{x_2}~0~\cdots~0~\overbrace{111\cdots11}^{x_k}\tag{1} 11111⋯11 x1​ 0 1111⋯11 x2​ 0 ⋯ 0 111⋯11 xk​(1)该 0 , 1 0,1 0,1 序列的构造方法是：将长度为 x i x_i xi​ 的 1 1 1 串之间用 0 0 0 隔开，不难发现整个序列中 0 0 0 有 k − 1 k-1 k−1 个， 1 1 1 有 r r r 个，所以形如 ( 1 ) (1) (1) 的序列可以视为如下多重集的一个全排列： M ′ = { r ⋅ 1 , ( k − 1 ) ⋅ 0 } M'=\{r\cdot1,(k-1)\cdot0\} M′={r⋅1,(k−1)⋅0}那么回顾在《多重集合排列》中给出的定理，我们知道这样的全排列数量为： ( k − 1 + r ) ! r ! ⋅ ( k − 1 ) ! = ( k − 1 + r r ) \frac{\big(k-1+r\big)!}{r!\cdot\big(k-1\big)!}=\binom{k-1+r}{r} r!⋅(k−1)!(k−1+r)!​=(rk−1+r​)

• 【证明.2】相较于证明 1 1 1，证明 2 2 2 稍显复杂，但其中用的原理都是类似的。即离散数学中关于映射的如下定理：对于给定的任意集合(即包括无限集合) A , B A,B A,B，如果有一个从 A A A 到 B B B 的双射函数，那么称 A A A 和 B B B 等势，即 ∣ A ∣ = ∣ B ∣ . |A|=|B|. ∣A∣=∣B∣. 另外关于集合的势，有着很显然但意义深远的三歧性定理：给定集合 A , B A,B A,B，那么 ∣ A ∣ < ∣ B ∣ , ∣ A ∣ = ∣ B ∣ , ∣ A ∣ > ∣ B ∣ |A|<|B|,|A|=|B|,|A|>|B| ∣A∣<∣B∣,∣A∣=∣B∣,∣A∣>∣B∣ 中恰有一个成立。
• 在上一部分的证明中，我们将多重集 r r r 组合数量通过双射函数转化为方程 ( ∗ ) (*) (∗) 的非负整数解数量，并后续通过形如 ( 1 ) (1) (1) 的 0 , 1 0,1 0,1 序列来表示非负整数解，最终得到结果。
• 构造多重集： M ′ = { ∞ ⋅ 1 , ∞ ⋅ 2 , ⋯ , ∞ ⋅ k } M'=\{\infin\cdot1,\infin\cdot2,\cdots,\infin\cdot k\} M′={∞⋅1,∞⋅2,⋯,∞⋅k}以及映射 f : M f:M f:M 的 r r r 组合全体 → \rightarrow → M ′ M' M′ 的 r r r 组合全体，如下： { x 1 ⋅ a 1 , x 2 ⋅ a 2 , ⋯ , x k ⋅ a k } ⟼ { 1 , ⋯ , 1 ⏞ x 1 , 2 , ⋯ , 2 ⏞ x 2 , ⋯ , k , ⋯ , k ⏞ x k } \{x_1\cdot a_1,x_2\cdot a_2,\cdots,x_k\cdot a_k\}\longmapsto\{\overbrace{1,\cdots,1}^{x_1},\overbrace{2,\cdots,2}^{x_2},\cdots,\overbrace{k,\cdots ,k}^{x_k}\} {x1​⋅a1​,x2​⋅a2​,⋯,xk​⋅ak​}⟼{1,⋯,1 ​x1​​,2,⋯,2 ​x2​​,⋯,k,⋯,k ​xk​​}其中 { x i } \{x_i\} {xi​} 满足和为 r r r 的约束，不难证明 f f f 是一个双射函数。
• 构造集合： M ′ ′ = { 1 , 2 , ⋯ , k + r − 1 } M''=\{1,2,\cdots,k+r-1\} M′′={1,2,⋯,k+r−1}以及映射 g : M ′ g:M' g:M′ 的 r r r 组合全体 → M ′ ′ \rightarrow M'' →M′′ 的 r r r 组合全体，如下： { b 1 , b 2 , ⋯ , b r } ⟼ { b 1 + 0 , b 2 + 1 , ⋯ , b r + r − 1 } \{b_1,b_2,\cdots,b_r\}\longmapsto\{b_1+0,b_2+1,\cdots,b_r+r-1\} {b1​,b2​,⋯,br​}⟼{b1​+0,b2​+1,⋯,br​+r−1}不难证明 g g g 也是一个双射函数，这里我们不妨假设 1 ≤ b 1 ≤ b 2 ≤ ⋯ ≤ b r ≤ k 1\leq b_1\leq b_2\leq\cdots\leq b_r\leq k 1≤b1​≤b2​≤⋯≤br​≤k，那么则有： b i + i − 1 ≤ b i + 1 + i − 1 < b i + 1 + i (2) b_i+i-1\leq b_{i+1}+i-1<b_{i+1}+i\tag{2} bi​+i−1≤bi+1​+i−1<bi+1​+i(2)于 ( 2 ) (2) (2) 式中取遍 i = 1 , 2 , ⋯ , r − 1 i=1,2,\cdots,r-1 i=1,2,⋯,r−1，分别能够得到： b 1 + 0 < b 2 + 1 b_1+0<b_2+1 b1​+0<b2​+1 b 2 + 1 < b 3 + 2 b_2+1<b_3+2 b2​+1<b3​+2 ⋯ \cdots ⋯ b r − 1 + r − 2 < b r + r − 1 b_{r-1}+r-2<b_r+r-1 br−1​+r−2<br​+r−1因此 { b 1 + 0 , b 2 + 1 , ⋯ , b r + r − 1 } \{b_1+0,b_2+1,\cdots,b_r+r-1\} {b1​+0,b2​+1,⋯,br​+r−1} 是集合 M ′ ′ M'' M′′ 的一个 r r r 组合，并且其数量显然为： ( k − 1 + r r ) \binom{k-1+r}{r} (rk−1+r​)基于前面给出的集合势的定理，我们知道，多重集 M M M 的 r r r 组合数量也由上式给出。

• 【定理】稍加改变，对于给定的多重集 M = { ∞ ⋅ a 1 , ∞ ⋅ a 2 , ⋯ , ∞ ⋅ a k } M=\{\infin\cdot a_1,\infin\cdot a_2,\cdots,\infin\cdot a_k\} M={∞⋅a1​,∞⋅a2​,⋯,∞⋅ak​}，要求其 r r r 排列中 a i a_i ai​ 都至少出现一次， r ≥ k r\geq k r≥k，这样的 r r r 组合数为： ( r − 1 k − 1 ) \binom{r-1}{k-1} (k−1r−1​)
• 【证明】可以类比上面的证明 1 1 1 完成， r r r 组合数等于方程： x 1 + x 2 + ⋯ + x k = r x_1+x_2+\cdots+x_k=r x1​+x2​+⋯+xk​=r 解个数，其中 x i x_i xi​ 须满足 x i ≥ 1 x_i\geq1 xi​≥1，因此我们令 y i = x i − 1 y_i=x_i-1 yi​=xi​−1，则将 ( ∗ ) (*) (∗) 式改写如下： y 1 + y 2 + ⋯ + y k = r − k (**) y_1+y_2+\cdots+y_k=r-k\tag{**} y1​+y2​+⋯+yk​=r−k(**)此时满足条件的 r r r 组合数等于上述方程 ( ∗ ∗ ) (**) (∗∗) 的非负整数解，即为： ( ( k − 1 ) + ( r − k ) r − k ) = ( r − 1 r − k ) = ( r − 1 k − 1 ) \binom{(k-1)+(r-k)}{r-k}=\binom{r-1}{r-k}=\binom{r-1}{k-1} (r−k(k−1)+(r−k)​)=(r−kr−1​)=(k−1r−1​)证毕.