本篇随笔简单讲解一下数学中的多重集排列组合。

集合的概念是唯一性。

多重集的特点就是不唯一性。

也就是同一种元素可以在多重集里面多次出现。

也就是multiset。

假设多重集一共有\(N\)个元素。那么对这\(N\)个元素全排列，除掉相同元素的全排列的积即可。

也就是：

很显然，先把所有可能，也就是全排列处理出来，然后相同元素可以随意互换位置，按乘法原理除下去就行。

多重集组合数这里比较难想。好好理解。

如果正着想，反正蒟蒻智商没有太通。

不妨反着来：对于有\(N\)种元素的多重集\(S\)，选\(K\)个元素，注意是个不是种，的可行方案数。可以变成：现在有\(N\)个篮子，把\(K\)个元素扔进这些篮子里的方案数。

注意，这种是特殊情况，也就是说，每种元素无限多个可供挑选。

这样的话，用隔板法解决问题。

容易得出，答案也就是\(C_{N+K-1}^{N-1}\)。

解释一下，现在有\(K\)个元素，分成\(N\)堆，也就是要往里插入\(N-1\)块板。按理讲应该是\(C_{K+1}^{N-1}\)，但是因为允许有空集，也就是不插，那么就相当于每块板子插进去之后又产生了新元素，所以是这个答案。

那么，根据多重集的限制，现在每种元素有一个数量上限，怎么办呢？

很简单，采用容斥原理。关于容斥原理，请见：

浅谈容斥原理

上限是“至多放\(f[i]\)个”，那么如果我往这个里面放\(f[i]+1\)个，是不是就不合法了？

把不合法的减去即可。

式子就不写了，大家知道这么回事就行。

推荐例题：

CF451E