C++离散与组合数学之多重集合 C多重集合的离散数学(2)

C++离散与组合数学之多重集合

如果遇到求多重集的全排列问题时，可直接套用公式。

如求多重集合S={4*2,2*6,1*7,3*4}的全排列。

• 先求多重集合中元素的个数：n=4+2+1+3=10。
• 套用公式：res=10!/4!*2!*1!*3!=12600。

多重集的非全排列

所有元素的重复度大于排列数：如s={4*2,4*3,5*4,4*6}。

从集合中选择r=4个数字的非全排列数。

注意，这里的排列数4小于、等于集合中重复度最小的数。

对于排列中的每一个位置都有k（为集合中元素的个数）种选择。

根据乘法原理，总排列数k*k*k*=kr。

某些元素重复度小于排列数

如果有一个元素的重复度小于选取个数 ,如S = { 3*a,2*b,1*c}多重集的三排列 , 可以使用包含排斥原理 、生成函数进行计算 ;

4. 容斥原理

容斥原理的目的：计数时，使重复的元素不被计算在内。

容斥流程：

先不考虑重叠的情况，把包含于某要求的所有元素的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗 漏又无重复。

两个集合的容斥实现

如有A、B两个有限集合。则，|A U B|=|A|+|B|-|A ∩ B|。用韦恩图表示：

Tips：|A|表示集合A的长度。