数组合数学

多重集的组合数

字数统计: 1.5k字   |   阅读时长: 6分
,

摘要: 多重集合的组合，推导与计算方法

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 组合数学1-排列组合 中我们详细梳理了组合数学的基本模型，以及排列组合的相关公式。进一步在文章 组合数 中，我们研究了编程求组合数的几个算法和代码模板，不过其中的集合是无重复的。

本文我们研究多重集合的排列、组合，以及计算方法和代码模板。

多重集

包含重复元素的广义集合：

物品 $a_{i}$ 有 $n_{i}$ 个，总物品个数为：

多重集的排列

结论

证明方法是转换为多重组合，也就是在 $n$ 个位置中选 $n_{1}$ 个给 $a_{1}$，然后从剩余的位置中选 $n_{2}$ 个给 $a_{2}$，以此类推，最后剩下的 $n_{t}$ 个给 $a_{t}$。

应用：多项式定理

有了多重集的排列，可以推出多项式定理。

建模：隔板法/捆绑法

  • 隔板法：分区域问题
  • 捆绑法： 相邻约束问题

多重集的组合

给定多重集 $S= \{n_{1} \cdot a_{1}, n_{2} \cdot a_{2}, …, n_{k} \cdot a_{k}\}$，给定整数 m。

问：从 S 中任取 m 个元素可以产生的不同多重集数量。

(1) $\forall i \in [1,k], m \leq n_{i}$

结论

证明

记各个物品选择情况为：$a_{i}$ 取了 $x_{i}$ 个，$\sum_{i=1}^{k}x_{i} = m$

目标是给每个 $x_{i}$ 赋值一个 $[0,m]$ 中的任意整数，且 $\sum_{i=1}^{k}x_{i} = m$

因为 $\forall i \in [1,k], m \leq n_{i}$，所以不用考虑 $x_{i} > n_{i}$ 的情况。

建模：隔板法

用 0 的个数表示每个 $x_{i}$ 的值，原问题可以转化为：用 k - 1 个 1 将 m 个 0 分为 k 组的方案数，也就是多重集 $\{m \cdot 0, (k - 1) \cdot 1\}$ 的排列数

因此套用多重集排列数的公式

原问题中多重集的组合数为

(2) $m \leq \sum\limits_{i=1}\limits^{k}n_{i}$

结论

证明：容斥原理

用到容斥原理，参考文章 组合数学4-容斥原理,鸽巢原理。

首先不考虑 $n_{i}$ 的限制，则从其中取 m 个元素的方案数为 $\dbinom{k+m-1}{k-1}$。

以上结果里包含了 $x_{i} > n_{i}$ 的不合法方案。

记 $S_{i}$ 为至少包含 $n_{i}+1$ 个 $a_{i}$ 的多重集(即 $a_{i}$ 个数不合法的多重集) 数量。在上述结果中减去 $\sum\limits_{i}S_{i}$ 即可。

首先从 S 中选 $m - n_{i} - 1$ 个元素，构成 $S_{i}$，其方案数为 $\dbinom{k+m-n_{i}-2}{k-1}$。

减去了所有只考虑 $x_{i} > x_{i}$ 的不合法方案后，还多减去了 $|S_{i} \cup S_{j}| :=$ 包含至少 $n_{i} + 1$ 个 $a_{i}$ 和至少 $n_{j} + 1$ 个 $a_{j}$ 的多重集方案数。

把这部分加回来 : $\sum\limits_{1 \leq i,j \leq k,i!=j}\dbinom{k+m-n_{i}-n_{j}-3}{k-1}$。

反复容斥下去即得：

计算：位运算+组合数

枚举 $x \in [0, 2^{N}-1]$，若 x 在二进制下共有 p 位为 1，分别是第 $i_{1}, i_{2}, …, i_{p}$ 位，则这个 x 就代表上式中的一项：

特别地，x = 0 代表 $\dbinom{N+M-1}{N-1}$，这样就可以计算多重集组合数公式的每一项。对于每一项，要求一个组合数。

代码模板

多重集合 $\{n_{i} * a_{i}\}, i=1,2,…,k$，其中元素 $a_{i}$ 有 $n_{i}$ 个。求从中选出 m 个元素能够形成的不同多重集数量。代码模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int multiple_combination(const vector<ll>& n, ll m, int MOD)
{
    int ans = 0;
    int k = n.size();
    for(int x = 0; x <= pow(2, N) - 1; ++x)
    {
        // 枚举 x 中所有为 1 的位
        ll t = k + m;
        int p = 0; // x 中有 p 个 1
        for(int i = 0; i < k; ++i)
        {
            if(x >> i & 1)
            {
                ++p;
                t -= n[i];
            }
        }
        t -= (p + 1);
        if(t < 0 || t < k - 1) continue;
        if(p & 1)
            ans = (ans - C(t, k - 1, MOD) + MOD) % MOD;
        else
            ans = (ans + C(t, k - 1, MOD)) % MOD;
    }
    return (ans + MOD) % MOD;
}

其中求组合数的过程，以 $\dbinom{N+M-1}{N-1} = P(N+M-1,N-1)/(N-1)!$ 为例，利用此公式时，有下面两种做法，细节参考文章 组合数：

  • 可以先求 $P(N + M - 1, N - 1) = (N + M - 1)(N + M - 2)…(M + 1)$，再乘以 $(N - 1)!$ 的乘法逆元。
  • Lucas 定理，注意先把 (N+M-1) 对 1e9+7 取模，再计算组合数，避免乘法结果超出 INT64 表示范围。
Share