106. 特殊的子集和：元检验(Special subset sums: meta-testing)

设$S(A)$是大小为$n$的集合$A$中所有元素的和，若任取集合$A$中的任意两个非空且没有交集的子集$B$和$C$都满足下面两个条件，我们就称$A$是的特殊的和集：

$S(B)\ne S(C)$，也就是说任意子集所有元素的和均不相同；

如果集合$B$中的元素比集合$C$多，则$S(B)>S(C)$。

在这个问题中我们假定集合中包含有$n$个严格单调递增的元素，并且已知其满足第二个条件。

令人惊奇的是，当$n=4$时，在所有可能的$25$组子集对中只有$1$组需要检验子集和是否相等(第一个条件)。同样的当$n=7$时，在所有可能的$966$组子集对中只有$70$组需要检验。

求当$n=12$时，在所有可能的$261625$组子集对中有多少组需要检验？

分析：根据题意，我们知道给定的集合已经满足第二个判断条件，也就是如果子集元素个数不相同时，两个子集的元素和必然不相同，这也就意味着我们只需要考虑两个子集元素个数相同的情况，考察他们的元素和是否相同。在做第103题和第105题时，我们可能已经发现对于某些子集对比如$B$和$C$，如果$B$中元素均在集合$C$中有一个对应比它大的元素，那么$S(B)$显然要小于$S(C)$，我们并不需要把元素和具体的求出来。

一、划分子集及比较大小的步骤

总体而言，我们可以把划分子集及比较大小的工作分为三步：

第一步：从集合$A$中选择偶数个元素：之所以要选择偶数个元素，是因为这样才能把它们划分成两个元素个数相同的子集。假设集合$A$的总元素个数为$n$个，选择元素个数为$2k$个，则总的方法数有$C_n^{2k}$种。
第二步：从$2k$个元素中选择$k$个元素组成一个子集，剩下的构成另一个子集，需要注意的是，具体哪个子集为$B$哪个子集为$C$并不影响比较两者的元素和，所以实际上需要比较次数只有$C_{2k}^k/2$次。
第三步：在不同的划分子集的方法中，有一些划分方法会使得两个子集的元素和大小是显然的，所以不需要做是否相等的比较。如对于集合$A=\{a_1,a_2,a_3,a_4\}$，假设其元素从左往右严格递增，则令$B=\{a_1,a_2\},C=\{a_3,a_4\}$，因为$B$中元素均可以在$C$中找到一个一一对应的比它大的元素，所以$S(B)$显然是小于$S(C)$的。同理如果$B=\{a_1,a_3\},C=\{a_2,a_4\}$，两者元素和的大小也是显然的。只剩下一种情况，即$B=\{a_1,a_4\},C=\{a_2,a_3\}$时，必须要把两者元素和都求出来，才知道两者是否相等。因此，我们需要从第二步所确定的方法数中扣除那些不需要做相等比较的数量。

现在问题的核心转变为如何确定不需要做比较，也就是两者之间元素和大小是显然的子集划分的方法数。

二、无需求和确定大小的子集划分方法数

还是接着上面的例子，对于严格递增的集合$A=\{a_1,a_2,a_3,a_4\}$，我们可以使用如下方式来表示不同的子集划分方法：从左往右如果元素被分在了第一个集合，则我们写下一个$'1'$，同理如果某个元素被分到了第二个集合，则我们写下一个$'2'$，则如果我们把$a_1,a_2$分到了第一个集合，把$a_3,a_4$分到了第二个集合，则这种划分方法可以简化表示为$'1122'$。同理，我们还可以把剩下两种划分方法表示为$'1212'$和$'1221'$，分别对应$\{a_1,a_3\},\{a_2,a_4\}$和$\{a_1,a_4\},\{a_2,a_3\}$这两种划分方法。

因为我们的元素是从左往右严格递增的，因此如果我们能尽量把左边的元素放在第一个集合，把右边的元素放在第二个集合，那么第一个集合的元素和显然会小于第二个集合的元素和，两者也就不需要通过求元素和的方式来做比较了。参照我们的记法，也就是要让$'1'$尽量集中在左边，而$'2'$集中在右边。更明确地说，我们要让这个由$'1','2'$组成的字符串，当从左向右数时，截止到任意一位，出现$'1'$的次数都要大于等于出现$'2'$的次数。比如对于$'1122'$，截止到第二位$'1'$出现了两次，$'2'$出现了零次；截止到第三位，$'1'$出现了两次，$'2'$出现了一次；截止到第四位，$'1'$出现了两次，$'2'$出现了两次，符合我们上面提到的条件，所以它表示的划分子集的方法就不用再做比较了。反之对于$'1221'$，截止到第三位，$'1'$出现了一次，而$'2'$出现了两次，不符合上面说的条件，所以必须要通过求和的方式来确定两个集合元素和是否相等。

可能有的同学已经发现，这种排列数字的方式正是一种dyck word，而对于一个长度为$2k$的由两种字符组成的字符串，其中是dyck word的数量为$C_k$，这里的$C_k$是一个卡特兰数，如第零到第六项的卡特兰数分别为$1, 1, 2, 5, 14, 42$，其计算公式为$C_{2k}^k/(k+1)$。因此，综合上面我们提到的三步，对于一个元素个数为$n$集合，从中选择$2k$个元素构成子集，并排除那些不需要做比较的子集划分方式，则剩下确实需要做检验的方法数为：

$$ N( k) =C_{n}^{2k}\left(\frac{C_{2k}^{k}}{2} -C_{k}\right) =C_{n}^{2k}\left(\frac{C_{2k}^{k}}{2} -\frac{C_{2k}^{k}}{k+1}\right) =C_{n}^{2k} C_{2k}^{k}\left(\frac{1}{2} -\frac{1}{k+1}\right) $$

则对于总元素个数为$n$的集合，两个子集总的元素个数可取$[2,n]$的所有偶数，也即$k$的取值范围为$[ 1,\lfloor n/2\rfloor ]$ 内所有整数，则最终需要检验做检验的次数为：

$$ T( n) =\sum _{k=1}^{\lfloor n/2\rfloor }\left( C_{n}^{2k}\left(\frac{C_{2k}^{k}}{2} -\frac{C_{2k}^{k}}{k+1}\right)\right) $$

代码实现上，我们就只需要把上述公式翻译成代码就可以了，具体如下：

# time cost = 6.35 µs ± 191 ns

from math import factorial as fac

def comb_num(n,k):
    num = fac(n)//(fac(n-k)*fac(k))
    return num

def main(N=12):
    res = 0
    for i in range(1,N//2+1):
        res += comb_num(N,2*i)*(comb_num(2*i,i)//2-comb_num(2*i,i)//(i+1))
    return res

本站所有文章如非特别声明皆为原创，转载请与作者本人联系并注明出处(原文链接)。如对文章有任何疑问或需指出错误，可以此页面提出问题，我会尽量及时回复。

←返回主页