去相邻的排列组合题【有点难】

wyl1267 2010-05-05 09:17:58

此题看似简单，其实有点难度，解题方法不限（用程序或数学推导均可）

1 1 2 2 3 3 4 4 5 5 组成一个十位数，相同的不能相邻，有多少种排法?

...全文

403 30 打赏收藏转发到动态举报

写回复

用AI写文章

30 条回复

切换为时间正序

请发表友善的回复…

发表回复

寒果 2010-05-26

打赏
举报

应该是10*8！＝403200

jinhaize 2010-05-25

打赏
举报

mark

wyl1267 2010-05-11

打赏
举报

#26楼的程序很精简，可没有注释，读起来挺费劲，能解释一下吗？
谢谢！

Sunday 2010-05-08

打赏
举报

结果是：

39480
Press any key to continue

程序如下：

#include<iostream>
using namespace std;
int a[11]={1,1,2,2,3,3,4,4,5,5};
int b[10];
#define N 10
int num()
{
int i,j,g;int sum=0;
b[0]=0;i=0;
while(1)
{
g=1;

for(j=i-1;j>=0;--j)
if(b[j]==b[i])
g=0;
if(i>0&&a[b[i]]==a[b[i-1]])g=0;
if(i==N-1&&g)
{
sum++;
for(j=0;j<N;++j)
printf( "%d ",a[b[j]]);
cout<<endl;
}
if(i<N-1&&g){i++;b[i]=0;continue;}
while(b[i]==9)i--;
if(i<0)break;
else b[i]++;
}
return sum/32;
}
int main()
{
cout<<num()<<endl;
return 0;
}

Sunday 2010-05-08

打赏
举报

http://acm.hdu.edu.cn/showproblem.php?pid=1030

Arucart 2010-05-07

打赏
举报

验证了下。。。的确是39480

yyfhz 2010-05-07

打赏
举报

[Quote=引用 14 楼 zeroieme 的回复:]
=10!/(2^5)-9!*C(5,1)/(2^4)+8!*C(5,2)/(2^3)-7!*C(5,3)/(2^2)+6!*C(5,4)/(2^1)-5!
=39480
[/Quote]
这个是对的，我之前的递推公式有错，NC了。
这个利用了集合的容斥性原理。简单的讲，假设有两个集合A和B，它们的面积分别为S(A)和S(B)，则
S(A∪B)= S(A)+S(B)- S(A∩B)
================================================================
现在要证明对于任意n个集合{Ai|i=1...n)，都有
S(∪Ai|i=1..n)=-∑S(∩{At|t=1..n},i)*(-1)^i, i=1..n
这里的∑S(∩{At|t=1..n},i)是一种写法，表示从A1,...,An个集合中任意抽取i个元素做交集，再把这些交集的面积加起来。
利用归纳法。
当n=2时,
S(A1∪A2)=S(A1)+S(A2)- S(A1∩A2)= -∑S(∩{At|t=1..2},1)*(-1)^1 -∑S(∩{At|t=1..2},2)*(-1)^2
当n=3时，
S(A1 ∪ A2 ∪ A3)
= S(A1∪A2)+S(A3)-S( (A1∪A2) ∩ A3)
= S(A1∪A2)+S(A3)-S((A1∩A3)∪(A2∩A3))
= S(A1)+S(A2)-S(A1∩A2)+S(A3)-[ S(A1∩A3) + S(A2∩A3) - S((A1∩A3)∩(A2∩A3))]
= S(A1)+S(A2)+S(A3)-S(A1∩A2)-S(A2∩A3)-S(A1∩A3)+S(A1∩A2∩A3)
= ∑S({A1,A2,A3},1)-∑S({A1,A2,A3},2)+∑S({A1,A2,A3},3)
= -∑S(∩{At|t=1..3},i)*(-1)^i, i=1..3

现假设n=k时成立，即有
S(∪Ai|i=1..k)=-∑S(∩{At|t=1..k},i)*(-1)^i, i=1,...,k)
则当n=k+1时，有

S(∪Ai| i=1..k+1)
= S((∪Ai|i=1..k)∪Ak+1)
= S(∪Ai|i=1..k)+S(Ak+1)-S((∪Ai|i=1..k)∩Ak+1)
= [-∑S(∩{At|t=1..k},i)*(-1)^i, i=1..k] + S(Ak+1) - S(∪(Ai∩Ak+1)|i=1..k)
= [-∑S(∩{At|t=1..k},i)*(-1)^i, i=1..k] + S(Ak+1) - [-∑S(∩{At∩Ak+1|t=1..k},i)*(-1)^i, i=1..k]
= ∑S(∩{At|t=1..k},1) + S(Ak+1) +[-∑S(∩{At|t=1..k},i)*(-1)^i, i=2..k]+∑S(∩{At∩Ak+1|t=1..k},i)*(-1)^i, i=1..k-1]+∑S(∩{At∩Ak+1|t=1..k},k)*(-1)^k .........(1)
注意到
① ∑S(∩{At|t=1..k},1)= ∑S(At), t=1..k ，因此有 ∑S(∩{At|t=1..k},1) + S(Ak+1)=∑S(At), t=1..k+1=∑S(∩{At|t=1..k+1},1)=-∑S(∩{At|t=1..k+1},1)*(-1)^1
② [∑S(∩{At∩Ak+1|t=1..k},i)*(-1)^i, i=1..k-1] = -[∑S(∩{At∩Ak+1|t=1..k},i-1)*(-1)^i, i=2..k]
③ -∑S(∩{At|t=1..k},i)*(-1)^i, i=2..k] - [∑S(∩{At∩Ak+1|t=1..k},i-1)*(-1)^i, i=2..k]=-∑S(∩{At|t=1..k+1},i)*(-1)^i, i=2..k]
④ ∑S(∩{At∩Ak+1|t=1..k},k)*(-1)^k= -∑S(∩{At∩Ak+1|t=1..k},k)*(-1)^(k+1)=-∑S(∩{At|t=1..k+1},k+1)*(-1)^(k+1)

因此(1)=-∑S(∩{At|t=1..k+1},1)*(-1)^1 -∑S(∩{At|t=1..k+1},i)*(-1)^i, i=2..k] -∑S(∩{At|t=1..k+1},k+1)*(-1)^(k+1)
= -∑S(∩{At|t=1..k+1},i)*(-1)^i, i=1..k+1

证毕。
===============================================
在本题中，其实可以取k=5 ，对应的集合Ai则表示数字i在整个字符串中连续出现的情况，要求S(∪Ai|i=1..5)。最后让全集10!/2^5减去S(∪Ai|i=1..5)即可，结果就是14楼的式子

wyl1267 2010-05-07

打赏
举报

[Quote=引用 14 楼 zeroieme 的回复:]
=10!/(2^5)-9!*C(5,1)/(2^4)+8!*C(5,2)/(2^3)-7!*C(5,3)/(2^2)+6!*C(5,4)/(2^1)-5!
=39480
[/Quote]

请哪位高手写个程序，验证此结果.

michael122 2010-05-06

打赏
举报

第一项是全排列，第二项是减去有1对相邻的，但是多减了2对相邻的，第三项加回来。。。
这是离散数学里面的知识，上面的只是直观的分析，需要严格证明

LeonTown 2010-05-06

打赏
举报

没看明白，
能给解释一下吗。。。

[Quote=引用 14 楼 zeroieme 的回复:]
=10!/(2^5)-9!*C(5,1)/(2^4)+8!*C(5,2)/(2^3)-7!*C(5,3)/(2^2)+6!*C(5,4)/(2^1)-5!
=39480
[/Quote]

rolim 2010-05-06

打赏
举报

类似八皇后问题？

xinzaiyiqi 2010-05-05

打赏
举报

[Quote=引用 3 楼 flying_sb 的回复:]
先求全排列，再将相同相邻的排列减掉
[/Quote]
也是这个感觉

flying_sb 2010-05-05

打赏
举报

先求全排列，再将相同相邻的排列减掉

lz3771 2010-05-05

打赏
举报

[Quote=引用 14 楼 zeroieme 的回复:]
=10!/(2^5)-9!*C(5,1)/(2^4)+8!*C(5,2)/(2^3)-7!*C(5,3)/(2^2)+6!*C(5,4)/(2^1)-5!
=39480
[/Quote]

容斥原理的应用加上可重复排列

michael122 2010-05-05

打赏
举报

[Quote=引用 14 楼 zeroieme 的回复:]

=10!/(2^5)-9!*C(5,1)/(2^4)+8!*C(5,2)/(2^3)-7!*C(5,3)/(2^2)+6!*C(5,4)/(2^1)-5!
=39480
[/Quote]

此乃正解，赞！

LeonTown 2010-05-05

打赏
举报

我初步感觉是：
(C(5,1)*C(4,1)) * (C(4,1)*C(3,1)) * (C(3,1)*C(2,1)) * (C(2,1)*C(1,1))

yyfhz 2010-05-05

打赏
举报

好像是得用递归的方法~~。先把问题扩充为：有N组不同的字符，每组都由2个同样的字符组成。现在将这N组字符构成2N长度的字符串。问可构成多少种相邻字符不同的字符串？
=============================================
先定义两个函数F(X)和G(X)，F(X)表示由X组相同的字符相邻所组成的字符串的数量；G(X)表示由至少X组相同的字符相邻所组成的字符串。
================================================
X=N：
显然，F(N)=C(N,N)*N!*2^N/2^N，
G(N)=F(N)

X=N-1：
F(N-1)=C(N-1,N)*(N-1+2N-2(N-1))!*2^(N-1)/2^N - C(N-1,N)*G(N)
=C(N-1,N)*[(N+1)!/2^1 -G(N)]
G(N-1)=F(N-1)+G(N)
...

X=N-i
F(N-i)= C(N-i,N)*(N-i+2N-2(N-i))!*2^(N-i)/2^N - C(N-i,N)*G(N-i+1)
= C(N-i,N)*[(N+i)!/2^i - G(N-i+1)]
G(N-i)= F(N-i)+G(N-i+1)
...

X=1=N-(N-1)
F(1) = C(N-(N-1),N)*[(N+(N-1))!/2^(N-1) - G(2)]
= C(1,N)*[(2N-1)!/2^(N-1) - G(2)]
G(1) = F(1)+G(2)

X=0
F(0) = C(0,N)*[2N!/2^N - G(1)]
完毕