让我们先来理解题面中$n=4$时的例子。设集合中的四个元素从小到大分别是a、b、c、d且满足条件2，现考虑两个互不相交的子集A、B。
这样的子集对共有$25$组，这是因为：
若$|A|=1$，则$0 < |B| \le 3$，A共有$\binom{4}{1}=4$种取法，选定A后B可以有$2^3-1=7$种取法，总计$4\times7=28$。
若$|A|=2$，则$0 < |B| \le 2$，A共有$\binom{4}{2}=6$种取法，选定A后B可以有$2^2-1=3$种取法，总计$6\times3=18$。
若$|A|=3$，则$|B|=1$，A共有$\binom{4}{3}=4$种取法，选定A后显然B只有1种取法，总计$4\times1=4$。
此外，A、B可以交换顺序，因此共有$(28+18+4)/2=25$种情况。
若$|A|\neq|B|$，则条件2保证了$S(A)\neq S(B)$。若$|A|=|B|=1$，则由于集合中的元素各异，也无需再检验。
因此只有$|A|=|B|=2$的情况需要作计算，这样的情况共有$\binom{4}{2}/2=3$种：
若$A=\{a,b\}$、$B=\{c,d\}$，则由$a < c$, $b < d$可得$S(A)\neq S(B)$。
类似地，若$A=\{a,c\}$、$B=\{b,d\}$，则由$a < b$, $b < d$也可得$S(A)\neq S(B)$。
因此唯一需要作具体计算的只有$A=\{a,d\}$、$B=\{b,c\}$一种情况。
同样地，对$n=12$的情况，找出所有满足$|A|=|B|=k$且互不相交的子集A、B，其中k在2到6之间。将A、B中元素各自从小到大排序为$a_1,\ldots,a_k$以及$b_1,\ldots,b_k$，若$a_i < b_i$对$i=1,\ldots,k$都成立或$a_i > b_i$对$i=1,\ldots,k$都成立则无需检验，否则需要作具体计算。
按上述方式统计后将结果除以$2$ (因为A、B可以交换顺序)即得结果$21384$。
import itertools
n=12
s=0
for k in range(2,n/2+1):
for choice in itertools.combinations(range(n),2*k):
for a_ in itertools.combinations(choice, k):
a=sorted(list(a_))
b=sorted([i for i in choice if i not in a])
if not (all(a[i] < b[i] for i in range(k)) or all(a[i] > b[i] for i in range(k))):
s+=1
print s/2
|
