容斥原理 带禁止位的排列

带禁止位的排列

1棋盘问题

2列队跑问题

3圆桌问题

看这个课件特别详细

点击打开链接 http://www.docin.com/p-382205465.html


带禁止位的排列:

对于禁止位的描述:

令X1,X2,X3,...,Xn是集合{1,2,3,...,n}的子集(允许有空集),用P(x1,x2,...,xn)表示集合{1,2,3,...,n}的所有排列i1,i2,i3,...,in的集合,并要求:i1不在X1内,i2不在X2内,i3不在X3内,...,in不在Xn内。

1.错排问题

令X1={1},X2={2},...,Xn={n},则集合P{X1,X2,...,Xn}等于集合{1,2,...,n}中的满足:i1 != 1, i2 != 2, ..., in != n 的所有排列i1i2i3...in组成的集合。P(X1,X2,...,Xn)是{1,2,...,n}的错位排列。

故有|P(x1,x2,...,xn)| = Dn = n! - C(1,n) (n-1)! + C(2,n)(n-2)! - ... + (-1)^n C(n,n)(n-n)!

= n! (1 - 1/(1!) + 1/(2!) - ... + (-1)^n*1/(n!))

2.带禁止位的棋盘放车问题

棋盘放车时

相关文章
相关标签/搜索