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_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