文章目录

一、多重集组合 ( 所有元素重复度大于组合数 )二、多重集组合 所有元素重复度大于组合数 推导 1 ( 分割线推导 )二、多重集组合 所有元素重复度大于组合数 推导 2 ( 不定方程非负整数解个数推导 )

排列组合参考博客 :

【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )【组合数学】集合的排列组合问题示例 ( 排列 | 组合 | 圆排列 | 二项式定理 )【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 )【组合数学】排列组合 ( 排列组合示例 )【组合数学】排列组合 ( 多重集排列 | 多重集全排列 | 多重集非全排列 所有元素重复度大于排列数 | 多重集非全排列 某些元素重复度小于排列数 )

一、多重集组合 ( 所有元素重复度大于组合数 )

多重集 :

S={n1⋅a1,n2⋅a2,⋯,nk⋅ak},0≤ni≤+∞S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq n_i \leq +\inftyS={n1​⋅a1​,n2​⋅a2​,⋯,nk​⋅ak​},0≤ni​≤+∞

元素种类 :多重集中含有 kkk 种不同的元素 ,元素表示 :每个元素表示为 a1,a2,⋯,aka_1 , a_2 , \cdots , a_ka1​,a2​,⋯,ak​ ,元素个数 :每个元素出现的次数是 n1,n2,⋯,nkn_1, n_2, \cdots , n_kn1​,n2​,⋯,nk​ ,元素个数取值 :nin_ini​ 的取值要求是 大于 000 , 小于正无穷 +∞+ \infty+∞ ;

上述多重集的组合 , 当所有元素的重复度 nin_ini​ 组大于组合数 rrr 时, r≤nir \leq n_ir≤ni​ 时 , 多重集的组合数为

N=C(k+r−1,r)N= C(k + r - 1, r)N=C(k+r−1,r)

二、多重集组合 所有元素重复度大于组合数 推导 1 ( 分割线推导 )

多重集 :

S={n1⋅a1,n2⋅a2,⋯,nk⋅ak},0≤ni≤+∞S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq n_i \leq +\inftyS={n1​⋅a1​,n2​⋅a2​,⋯,nk​⋅ak​},0≤ni​≤+∞

取 rrr 种元素的组合 , r≤nir \leq n_ir≤ni​ , 推导过程如下 :

在 kkk 种元素中 , 取 rrr 种元素 , 每种元素取 0∼r0 \sim r0∼r 个不等的元素 ,

使用 k−1k-1k−1 个分割线分割 kkk 种元素的位置 , k−1k - 1k−1 个分割线相当于组成了 kkk 个盒子 , 在每个盒子中放 0∼r0 \sim r0∼r 个不等的元素 ,

放置的总元素的个数是 rrr 个 , 分割线个数是 k−1k-1k−1 个 , 这里就产生了一个组合问题 , 在 k−1k-1k−1 个分割线 和 rrr 个元素之间 , 选取 rrr 个元素 , 就是 多重集的 r≤nir \leq n_ir≤ni​ 情况下的 组合个数 ;

结果是 :

N=C(k+r−1,r)N= C(k + r - 1, r)N=C(k+r−1,r)

二、多重集组合 所有元素重复度大于组合数 推导 2 ( 不定方程非负整数解个数推导 )

多重集 :

S={n1⋅a1,n2⋅a2,⋯,nk⋅ak},0≤ni≤+∞S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq n_i \leq +\inftyS={n1​⋅a1​,n2​⋅a2​,⋯,nk​⋅ak​},0≤ni​≤+∞

取 rrr 种元素的组合 , r≤nir \leq n_ir≤ni​ , 推导过程如下 :

多重集 SSS 每个元素取值 :

第 111 种元素取值个数 :元素 a1a_1a1​ 的取值个数是 x1x_1x1​ ,

第 222 种元素取值个数 :元素 a2a_2a2​ 的取值个数是 x2x_2x2​ ,

⋮\; \; \, \ \ \ \ \ \ \vdots⋮

第 kkk 种元素取值个数 :元素 aka_kak​ 的取值个数是 xkx_kxk​ ;

不定方程 x1+x2+⋯+xk=rx_1 + x_2 + \cdots + x_k = rx1​+x2​+⋯+xk​=r ;

xix_ixi​ 可以为 000 , 即某个元素取值个数可以是 000 ;

则多重集 SSS 的 rrr 组合是 :{x1⋅a1,x2⋅a2,⋯,xk⋅ak}\{ x_1 \cdot a_1 , x_2 \cdot a_2 , \cdots , x_k \cdot a_k \}{x1​⋅a1​,x2​⋅a2​,⋯,xk​⋅ak​}

xix_ixi​ 的取值是非负整数

多重集组合与方程对应 :只要有一个 rrr 组合 , 就可以写出一个对象的 方程 x1+x2+⋯+xk=rx_1 + x_2 + \cdots + x_k = rx1​+x2​+⋯+xk​=r 出来 ;

非负整数解与多重集组合对应 :x1+x2+⋯+xk=rx_1 + x_2 + \cdots + x_k = rx1​+x2​+⋯+xk​=r 不定方程的一组非负整数解 , 就对应着 一个 SSS 多重集的 rrr 组合 ;

一一对应关系 :上述

方程的非负整数解的个数

与

SSS 多重集的 rrr 组合个数一一对应;

求 SSS 多重集的 rrr 组合数 , 就可以转化成 求 x1+x2+⋯+xk=rx_1 + x_2 + \cdots + x_k = rx1​+x2​+⋯+xk​=r 方程非负整数解个数 ;

将上述解写成一个序列, 序列中使用 k−1k-1k−1 个 000 , 分割 kkk 组 111 ;

1⋯1⏟x1个1\begin{matrix} \underbrace{ 1 \cdots 1 } \\ x_1个1 \end{matrix}1⋯1​x1​个1​ 000 1⋯1⏟x2个1\begin{matrix} \underbrace{ 1 \cdots 1 } \\ x_2个1 \end{matrix}1⋯1​x2​个1​ 000 1⋯1⏟x3个1\begin{matrix} \underbrace{ 1 \cdots 1 } \\ x_3个1 \end{matrix}1⋯1​x3​个1​ 000 ⋯\cdots⋯ 000 1⋯1⏟xk个1\begin{matrix} \underbrace{ 1 \cdots 1 } \\ x_k个1 \end{matrix}1⋯1​xk​个1​

不定方程每个解 都对应着 上述 k−1k-1k−1 个 000 和 rrr 个 111 的一个排列 ;

相当于一个多重集 S′={r⋅1,(k−1)⋅0}S' = \{ r \cdot 1 , (k-1) \cdot 0 \}S′={r⋅1,(k−1)⋅0} 的全排列 ;

这里就将 多重集的组合问题 , 转化成了 另外一个多重集的全排列问题 , 多重集全排列是有公式的 ;

多重集全排列的公式是 :( 回顾知识点 ① )

S={n1⋅a1,n2⋅a2,⋯,nk⋅ak},0≤ni≤+∞S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq n_i \leq +\inftyS={n1​⋅a1​,n2​⋅a2​,⋯,nk​⋅ak​},0≤ni​≤+∞

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

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

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

参考 :【组合数学】排列组合 ( 多重集排列 | 多重集全排列 | 多重集非全排列 所有元素重复度大于排列数 | 多重集非全排列 某些元素重复度小于排列数 ) 二、多重集全排列

( 回顾知识点完毕 ① )

可以根据上述公式 , 计算 多重集 S′={r⋅1,(k−1)⋅0}S' = \{ r \cdot 1 , (k-1) \cdot 0 \}S′={r⋅1,(k−1)⋅0} 的全排列 , 结果是 :

N=(r+k−1)!r!(k−1)!N = \cfrac{(r + k - 1) !}{ r! (k-1)! }N=r!(k−1)!(r+k−1)!​

★ 排列数与组合数回顾 :( 回顾知识点 ② )

排列数 :nnn 元集 SSS , 从 SSS 集合中 有序 , 不重复 选取 rrr 个元素 , P(n,r)=n!(n−r)!P(n,r) = \dfrac{n!}{(n-r)!}P(n,r)=(n−r)!n!​组合数 :nnn 元集 SSS , 从 SSS 集合中 无序 , 不重复 选取 rrr 个元素 , C(n,r)=P(n,r)r!n!(n−r)!r!C(n,r) = \dfrac{P(n,r)}{r!} \dfrac{n!}{(n-r)!r!}C(n,r)=r!P(n,r)​(n−r)!r!n!​

参考 :【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 )

( 回顾知识点完毕 ② )

由上述的组合数可以看出, N=(r+k−1)!r!(k−1)!N = \cfrac{(r + k - 1) !}{ r! (k-1)! }N=r!(k−1)!(r+k−1)!​

的值正好是从 r+k−1r + k - 1r+k−1 个元素中取 rrr 个元素的组合数 ;

N=(r+k−1)!r!(k−1)!=C(r+k−1,r)N = \cfrac{(r + k - 1) !}{ r! (k-1)! } = C(r + k - 1 , r)N=r!(k−1)!(r+k−1)!​=C(r+k−1,r)

【组合数学】排列组合 ( 多重集组合数 | 所有元素重复度大于组合数 | 多重集组合数 推导 1 分割线推导 | 多重集组合数 推导 2 不定方程非负整数解个数推导 )

如果觉得《【组合数学】排列组合 ( 多重集组合数 | 所有元素重复度大于组合数 | 多重集组》对你有帮助，请点赞、收藏，并留下你的观点哦！