多重集的排列组合问题

排列，英文名为Permutation，是指从某元素集合中取出指定个数的元素进行排序


组合，英文名为Combination，是指从某元素集合中仅仅取出指定个数的元素，不考虑排序


从有n个不同元素的集合任取r个元素的排列方式有：P(n, r) = n*(n-1)*...*(n-r+1) = n! / (n-r)!,特别地 P(n,n) = n!
从有n个不同元素的集合任取r个元素的组合方式有：C(n, r) = P(n, r) / r! = n! / ( (n-r)! * r!)，特别地C(n,n) = 1


二、下面我们来定义多重集合（multiset）的排列组合






设多重集合 S = { n1 * a1, n2 * a2, ..., nk * ak },n = n1 + n2 + ... + nk,


即集合 S 中含有n1个元素a1， n2个元素a2，...，nk个元素ak，ni被称为元素ai的重数，k成为多重集合的类别数


在 S 中任选 r 个元素的排列称为S的r排列，当r = n时，有公式 P(n; n1*a1, n2*a2, ..., nk*ak) = n! / (n1! * n2! * ...* nk!)


在 S 中任选 r 个元素的组合称为S的r组合，当r<=任意ni时，有公式 C(n; n1*a1, n2*a2, ..., nk*ak) = C(k+r-1, r),


由公式可以看出多重集合的组合只与类别数k 和选取的元素r 有关，与总数无关！