一道很难的排列组合题设n为正整数,S=
解答：
这是我做过最难的组合题目之一。
仔细分析也没能找到好的计算方法，只能根据条件详细计算了。
设这样的集合组A,B,C,D共有S(n)个
显然S(1)=0，以下不妨设n大于1，并记C(N,M)=N!/(M!(N-M)!)。
对于集合A，一共有∑(m=1,…,n)C(n,m)种可能。
对于每种C(n,m)，集合B一共有
∑(i=0,…,m)∑(j=0,…,n-m，i+j≠0)C(m,i)C(n-m,j)种可能。
对于每种C(m,i)C(n-m,j)，集合C一共有
∑(k=0,…,n-m-j)∑(l=0,…,m-i+j，k+l≠0)C(n-m-j,k)C(m-i+j,l...全部
解答：
这是我做过最难的组合题目之一。
仔细分析也没能找到好的计算方法，只能根据条件详细计算了。
设这样的集合组A,B,C,D共有S(n)个
显然S(1)=0，以下不妨设n大于1，并记C(N,M)=N!/(M!(N-M)!)。
对于集合A，一共有∑(m=1,…,n)C(n,m)种可能。
对于每种C(n,m)，集合B一共有
∑(i=0,…,m)∑(j=0,…,n-m，i+j≠0)C(m,i)C(n-m,j)种可能。
对于每种C(m,i)C(n-m,j)，集合C一共有
∑(k=0,…,n-m-j)∑(l=0,…,m-i+j，k+l≠0)C(n-m-j,k)C(m-i+j,l)种可能。
对于每种C(n-m-j,k)C(m-i+j,l)，集合D一共有2^(m+j+k)-1种可能。
所以，S(n)=∑(m=1,…,n)C(n,m)∑(i=0,…,m)∑(j=0,…,n-m，i+j≠0)C(m,i)C(n-m,j)∑(k=0,…,n-m-j)∑(l=0,…,m-i+j，k+l≠0)C(n-m-j,k)C(m-i+j,l)(2^(m+j+k)-1)。
=∑(m=1,…,n)∑(i=0,…,m)∑(j=0,…,n-m，i+j≠0)∑(k=0,…,n-m-j)∑(l=0,…,m-i+j，k+l≠0)C(n,m)C(m,i)C(n-m,j)C(n-m-j,k)C(m-i+j,l)(2^(m+j+k)-1)。
[例]当n=2时，集合组A,B,C,D最多只有3^4=81个，其中满足条件的共有S(2)=2*1*2*3+2*1*1*3+2*1*1*3+2*1*1*3+1*2*1*3=36（种），具体集合组A,B,C,D如下：
{1},{2},{1},{1}
{1},{2},{1},{2}
{1},{2},{1},{1,2}
{1},{2},{2},{1}
{1},{2},{2},{2}
{1},{2},{2},{1,2}
{1},{2},{1,2},{1}
{1},{2},{1,2},{2}
{1},{2},{1,2},{1,2}
{2},{1},{1},{1}
{2},{1},{1},{2}
{2},{1},{1},{1,2}
{2},{1},{2},{1}
{2},{1},{2},{2}
{2},{1},{2},{1,2}
{2},{1},{1,2},{1}
{2},{1},{1,2},{2}
{2},{1},{1,2},{1,2}
{1},{1},{2},{1}
{1},{1},{2},{2}
{1},{1},{2},{1,2}
{2},{2},{1},{1}
{2},{2},{1},{2}
{2},{2},{1},{1,2}
{1},{1,2},{2},{1}
{1},{1,2},{2},{2}
{1},{1,2},{2},{1,2}
{2},{1,2},{1},{1}
{2},{1,2},{1},{2}
{2},{1,2},{1},{1,2}
{1,2},{1},{2},{1}
{1,2},{1},{2},{2}
{1,2},{1},{2},{1,2}
{1,2},{2},{1},{1}
{1,2},{2},{1},{2}
{1,2},{2},{1},{1,2}
。
收起
