Skip to content

第六章 容斥原理

容斥原理

计数 S\displaystyle{ S } 中不具有性质 P1\displaystyle{ P _{ 1 } }P2\displaystyle{ P _{ 2 } } 的对象个数

  • 首先计数 S\displaystyle{ S } 中的所有对象
  • 然后排除具有性质 P1\displaystyle{ P _{ 1 } } 的所有对象
  • 再排除具有性质 P2\displaystyle{ P _{ 2 } } 的所有对象
  • 再重新加入具有性质 P1\displaystyle{ P _{ 1 } }P2\displaystyle{ P _{ 2 } } 的对象一次
    • 因为把这样的对象排除了两次

A1\displaystyle{ A _{ 1 } }S\displaystyle{ S } 中具有性质 P1\displaystyle{ P _{ 1 } } 的对象组成的子集,A2\displaystyle{ A _{ 2 } }S\displaystyle{ S } 中具有性质 P2\displaystyle{ P _{ 2 } } 的对象组成的子集,则

A1A2=SA1A2+A1A2\displaystyle{ \left|\overline{ A } _{ 1 } \cap \overline{ A } _{ 2 }\right| = \left| S \right| - \left| A _{ 1 } \right| - \left| A _{ 2 } \right| + \left| A _{ 1 } \cap A _{ 2 } \right| }

推广一下

A1A2Am=SAi+AiAj+(1)mA1A2Am\displaystyle{ \begin{aligned}\left|\overline{ A } _{ 1 } \cap \overline{ A } _{ 2 } \cap \ldots \overline{ A } _{ m }\right| & = \left| S \right| \\ & - \sum \left| A _{ i } \right| + \sum \left| A _{ i } \cap A _{ j } \right| - \ldots \\ & + \left( - 1 \right) ^{ m } \sum \left| A _{ 1 } \cap A _{ 2 } \cap \ldots \cap A _{ m } \right|\end{aligned} }

等式右边的总项数等于 2m\displaystyle{ 2 ^{ m } }

推论 6.1.2

集合 S\displaystyle{ S } 中至少具有性质 P1,,Pm\displaystyle{ P _{ 1 } , \ldots , P _{ m } } 之一的对象个数

A1A2Am=AiAiAj+AiAjAk+(1)m+1A1A2Am\displaystyle{ \begin{aligned}\left| A _{ 1 } \cup A _{ 2 } \cup \ldots \cup A _{ m } \right| & = \sum \left| A _{ i } \right| \\ & - \sum \left| A _{ i } \cap A _{ j } \right| + \sum \left| A _{ i } \cap A _{ j } \cap A _{ k } \right| - \ldots \\ & + \left( - 1 \right) ^{ m + 1 } \sum \left| A _{ 1 } \cap A _{ 2 } \cap \ldots \cap A _{ m } \right|\end{aligned} }

求 1 到 1000 之间不能被 5 整除,且不能被 6 整除,且不能被 8 整除的整数个数

P1,P2,P3\displaystyle{ P _{ 1 } , P _{ 2 } , P _{ 3 } } 分别表示能被这三个数整除

A1=10005=200,A2=10006=166,A3=10008=125A1A2=1000lcm(5,6)=33A1A3=1000lcm(5,8)=25A2A3=1000lcm(6,8)=100024=41A1A2A3=1000lcm(5,6,8)=1000120=8A1A2A3=1000(200+166+125)+(33+25+41)8=600\displaystyle{ \begin{aligned}& \left| A _{ 1 } \right| = \frac{ 1000 }{ 5 } = 200 , \left| A _{ 2 } \right| = \frac{ 1000 }{ 6 } = 166 , \left| A _{ 3 } \right| = \frac{ 1000 }{ 8 } = 125 \\ & \left| A _{ 1 } \cap A _{ 2 } \right| = \frac{ 1000 }{ \operatorname{lcm} \left( 5 , 6 \right) } = 33 \\ & \left| A _{ 1 } \cap A _{ 3 } \right| = \frac{ 1000 }{ \operatorname{lcm} \left( 5 , 8 \right) } = 25 \\ & \left| A _{ 2 } \cap A _{ 3 } \right| = \frac{ 1000 }{ \operatorname{lcm} \left( 6 , 8 \right) } = \frac{ 1000 }{ 24 } = 41 \\ & \left| A _{ 1 } \cap A _{ 2 } \cap A _{ 3 } \right| = \frac{ 1000 }{ \operatorname{lcm} \left( 5 , 6 , 8 \right) } = \frac{ 1000 }{ 120 } = 8 \\ & \left| \overline{ A } _{ 1 } \cap \overline{ A } _{ 2 } \cap \overline{ A } _{ 3 } \right| = 1000 - \left( 200 + 166 + 125 \right) + \left( 33 + 25 + 41 \right) - 8 = 600\end{aligned} }

带重复的组合

已证明具有 k\displaystyle{ k } 种不同对象且每种对象都有无限重数的多重集合的 r\displaystyle{ r } 组合的个数等于

(r+k1r)\displaystyle{ { r + k - 1 \choose r } }

确定多重集合 T={3a,4b,5c}\displaystyle{ T = \left\lbrace 3 \cdot a , 4 \cdot b , 5 \cdot c \right\rbrace } 的 10 组合数目

  • S:T={a,b,c}\displaystyle{ S : T ^{ \ast } = \left\lbrace \infty \cdot a , \infty \cdot b , \infty \cdot c \right\rbrace } 的所有 10 组合的集合
  • P1,P2,P3:T\displaystyle{ P _{ 1 } , P _{ 2 } , P _{ 3 } : T ^{ \ast } } 的 10 组合中 {a}>3,{b}>4,{c}>5\displaystyle{ \left\lbrace a \right\rbrace > 3 , \left\lbrace b \right\rbrace > 4 , \left\lbrace c \right\rbrace > 5 } 次的性质

A1=(6+316)\displaystyle{ \left| A _{ 1 } \right| = { 6 + 3 - 1 \choose 6 } } 含义为:由于 a\displaystyle{ a } 至少出现 4 次,那么先把这 4\displaystyle{ 4 } 次删了,组成一个 6 组合,从 a,b,c\displaystyle{ a , b , c } 中任意选择,即得到上面的式子

A1A2A3=S(A1+A2+A3)+(A1A2+A1A3+A2A3)A1A2A3=(10+3110)((6+316)+(5+315)+(4+314))+((1+311)+(0+310)+0)0=6\displaystyle{ \begin{aligned}\left| \overline{ A } _{ 1 } \cap \overline{ A } _{ 2 } \cap \overline{ A } _{ 3 } \right| & = \left| S \right| - \left( \left| A _{ 1 } \right| + \left| A _{ 2 } \right| + \left| A _{ 3 } \right| \right) \\ & + \left( \left| A _{ 1 } \cap A _{ 2 } \right| + \left| A _{ 1 } \cap A _{ 3 } \right| + \left| A _{ 2 } \cap A _{ 3 } \right| \right) \\ & - \left| A _{ 1 } \cap A _{ 2 } \cap A _{ 3 } \right| \\ & = { 10 + 3 - 1 \choose 10 } \\ & - \left( { 6 + 3 - 1 \choose 6 } + { 5 + 3 - 1 \choose 5 } + { 4 + 3 - 1 \choose 4 } \right) \\ & + \left( { 1 + 3 - 1 \choose 1 } + { 0 + 3 - 1 \choose 0 } + 0 \right) - 0 \\ & = 6\end{aligned} }

错位排列

在形成一个全排列的时候,任意一个数字 i\displaystyle{ i } 所在的位置都不再第 i\displaystyle{ i } 个上。

这样排列的数量为

Dn=n!(111!+12!13!++(1)n1n!)\displaystyle{ D _{ n } = {n !} \left( 1 - \frac{ 1 }{ {1 !} } + \frac{ 1 }{ {2 !} } - \frac{ 1 }{ {3 !} } + \ldots + \left( - 1 \right) ^{ n } \frac{ 1 }{ {n !} } \right) }
  • S\displaystyle{ S }: 自然数 1 到 n\displaystyle{ n } 的全部排列的集合
  • Pj\displaystyle{ P _{ j } }: 一个排列中 j\displaystyle{ j } 不再他自然位置上的性质
  • A1=Aj=(n1)!\displaystyle{ \left| A _{ 1 } \right| = \left| A _{ j } \right| = {\left( n - 1 \right) !} }
  • A1A2=AiAj=(n2)!\displaystyle{ \left| A _{ 1 } \cap A _{ 2 } \right| = \left| A _{ i } \cap A _{ j } \right| = {\left( n - 2 \right) !} }
  • A1A2Ak=(nk)!\displaystyle{ \left| A _{ 1 } \cap A _{ 2 } \cap \ldots \cap A _{ k } \right| = {\left( n - k \right) !} }
Dn=A1A2An=n!(n1)(n1)!+(n2)(n2)!+(1)n(nn)0!\displaystyle{ \begin{aligned}D _{ n } & = \left| \overline{ A } _{ 1 } \cap \overline{ A } _{ 2 } \cap \ldots \overline{ A } _{ n } \right| \\ & = {n !} - { n \choose 1 } {\left( n - 1 \right) !} + { n \choose 2 } {\left( n - 2 \right) !} - \ldots + \left( - 1 \right) ^{ n } { n \choose n } {0 !}\end{aligned} }

有性质:任意一个全排列中错位排列的概率为 Dnn!1e\displaystyle{ \frac{ D _{ n } }{ {n !} } \approx \frac{ 1 }{ e } }

递推公式

Dn=(n1)(Dn1+Dn2)\displaystyle{ D _{ n } = \left( n - 1 \right) \left( D _{ n - 1 } + D _{ n - 2 } \right) } Dn=nDn1+(1)n\displaystyle{ D _{ n } = n D _{ n - 1 } + \left( - 1 \right) ^{ n } }

带有禁止位置的排列

X1,X2,,Xn\displaystyle{ X 1 , X 2 , \ldots , X n }{1,2,,n}\displaystyle{ \left\lbrace 1 , 2 , … , n \right\rbrace } 的子集,用 P(X1,X2,,Xn)\displaystyle{ P \left( X 1 , X 2 , … , X n \right) } 表示 {1,2,,n}\displaystyle{ \left\lbrace 1 , 2 , … , n \right\rbrace } 的所有排列 i1i2in\displaystyle{ i _{ 1 } i _{ 2 } … i _{ n } } 的集合:使得 ik\displaystyle{ i _{ k } } 不在 Xk\displaystyle{ X _{ k } } 内。其数目用 p(X1,X2,,Xn)=P(X1,X2,,Xn)\displaystyle{ p \left( X 1 , X 2 , … , X n \right) = \left| P \left( X 1 , X 2 , … , X n \right) \right| } 表示

n=5,X1={1,4},X2={3},X3=,X4={1,5},X5={2,5}\displaystyle{ n = 5 , X _{ 1 } = \left\lbrace 1 , 4 \right\rbrace , X _{ 2 } = \left\lbrace 3 \right\rbrace , X _{ 3 } = \varnothing , X _{ 4 } = \left\lbrace 1 , 5 \right\rbrace , X _{ 5 } = \left\lbrace 2 , 5 \right\rbrace }。则P(X1,X2,,Xn)\displaystyle{ P \left( X 1 , X 2 , \ldots , X n \right) } 中的排列与下图所示的在棋盘上有禁止位置的 5 个非攻击型车的放置一一对应

xx
x
xx
xx

n 个非攻击型不可区分的车放到带有禁止放置位置的 nn 列棋盘上的放置方法数等于

n!r1(n1)!+r2(n2)!+(1)krk(nk)!++(1)nrn\displaystyle{ {n !} - r _{ 1 } {\left( n - 1 \right) !} + r _{ 2 } {\left( n - 2 \right) !} - \ldots + \left( - 1 \right) ^{ k } r _{ k } {\left( n - k \right) !} + \ldots + \left( - 1 \right) ^{ n } r _{ n } }
  • S: n 个非攻击型车在 nn 列棋盘上的所有放置方法的集合
  • Pj\displaystyle{ P _{ j } }: 在第 j 行上的车是在属于 Xj\displaystyle{ X _{ j } } 的列上
  • A1=X1(n1)!,Ai=Xi(n1)!\displaystyle{ \left| A _{ 1 } \right| = \left| X _{ 1 } \right| {\left( n - 1 \right) !} , \left| A _{ i } \right| = \left| X _{ i } \right| {\left( n - 1 \right) !} }
  • ΣAi=r1(n1)!\displaystyle{ \Sigma \left| A _{ i } \right| = r _{ 1 } {\left( n - 1 \right) !} }r1\displaystyle{ r _{ 1 } } 等于棋盘上禁止放车的格子数
  • ΣAiAj=r2(n2)!\displaystyle{ \Sigma \left| A _{ i } \cap A _{ j } \right| = r _{ 2 } {\left( n - 2 \right) !} }r2\displaystyle{ r _{ 2 } } 等于把两个非攻击型车放到棋盘禁止位置上的方法数
  • ΣAi1Ai2Aik=rk(nk)!\displaystyle{ \Sigma \left| A _{ i _{ 1 } } \cap A _{ i _{ 2 } } \cap \ldots \cap A _{ i _{ k } } \right| = r _{ k } {\left( n - k \right) !} }rk\displaystyle{ r _{ k } } 等于把 k 个非攻击型车放到棋盘禁止位置上的方法数
x
xx
xx
xx
  • r1=7\displaystyle{ r _{ 1 } = 7 }
  • r2\displaystyle{ r _{ 2 } }C42\displaystyle{ C _{ 4 } ^{ 2 } } 种行选项中来选,共 15 种
    • 1, 2: 1 种
    • 1, 3: 2 种
    • 1, 4: 2 种
    • 2, 3: 4 种
    • 2, 4: 4 种
    • 3, 4: 2 种
  • r3\displaystyle{ r _{ 3 } }C43\displaystyle{ C _{ 4 } ^{ 3 } } 种行选项种来选,共 10 种
    • 1, 2, 3: 2 种
    • 1, 2, 4: 2 种
    • 1, 3, 4: 2 种
    • 2, 3, 4: 2x2=4 种
  • r4=2\displaystyle{ r _{ 4 } = 2 }
  • r5=r6=0\displaystyle{ r _{ 5 } = r _{ 6 } = 0 }

总方法数为 6!7×5!+15×4!10×3!+2×2!=184\displaystyle{ 6 !- 7 \times {5 !} + 15 \times 4 !- 10 \times {3 !} + 2 \times {2 !} = 184 }

另一个禁止位置问题

第二天排队,前面的人与第一天不同。即不出现 12, 23, … 这种连续的排列

  • A1=Aj=(n1)!\displaystyle{ \left| A _{ 1 } \right| = \left| A _{ j } \right| = {\left( n - 1 \right) !} }
  • A1A2=AiAj=(n2)!\displaystyle{ \left| A _{ 1 } \cap A _{ 2 } \right| = \left| A _{ i } \cap A _{ j } \right| = {\left( n - 2 \right) !} }
  • Qn=A1A2Am=Dn+Dn1\displaystyle{ Q _{ n } = \left| \overline{ A } _{ 1 } \cap \overline{ A } _{ 2 } \cap \ldots \cap \overline{ A } _{ m } \right| = D _{ n } + D _{ n - 1 } }

莫比乌斯反演

  • Xn={1,2,,n}\displaystyle{ X _{ n } = \left\lbrace 1 , 2 , \ldots , n \right\rbrace },偏序集 (P(Xn),)\displaystyle{ \left( \mathcal{ P } \left( X _{ n } \right) , \subseteq \right) }
  • F:P(Xn)R\displaystyle{ F : \mathcal{ P } \left( X _{ n } \right) \to \mathbb{R} } 是定义在 P(Xn)\displaystyle{ \mathcal{ P } \left( X _{ n } \right) } 上的实值函数
  • 使用 F\displaystyle{ F } 定义一个新函数 G:P(Xn)R\displaystyle{ G : \mathcal{ P } \left( X _{ n } \right) \to \mathbb{R} },其中 G(K)=LKF(L)\displaystyle{ G \left( K \right) = \sum _{ L \subseteq K } F \left( L \right) }KXn\displaystyle{ K \subseteq X _{ n } }
  • 莫比乌斯反演可将上式反解 F(K)=LK(1)KLG(L)\displaystyle{ F \left( K \right) = \sum _{ L \subseteq K } \left( - 1 \right) ^{ \left| K \right| - \left| L \right| } G \left( L \right) }

代数结构的判定,循环群的计算

子群

<G,>,<H,>\displaystyle{ < G , \circ > , < H , \circ > } HG,H,<H,> is Group\displaystyle{ H \subseteq G , H \ne \varnothing , < H , \circ > \text{ is Group} }

判定定理

G\displaystyle{ G } 是群,HG,H\displaystyle{ H \subseteq G , H \ne \varnothing }H\displaystyle{ H }G\displaystyle{ G } 的子群当且仅当 x,yH,xy1H\displaystyle{ \forall x , y \in H , x y ^{ {-1 } } \in H }

充分性:设 G\displaystyle{ G } 是群,HG,H\displaystyle{ H \subseteq G , H \ne \varnothing }H\displaystyle{ H }G\displaystyle{ G } 的子群

  • 封闭性
  • 结合率
  • 幺元 eH\displaystyle{ e \in H },取 y=x,xx1=eH\displaystyle{ y = x , x x ^{ {-1 } } = e \in H }
  • 全员可逆

必要性

F(X)={f:X×XRx,yX,xyf(x,y)=0}\displaystyle{ \mathscr{ F } \left( X \right) = \left\lbrace f : X \times X \to \mathbb{R} \mid \forall x , y \in X , x \cancel{ \preceq } y \to f \left( x , y \right) = 0 \right\rbrace } h(x,y)={{z:xzy}f(x,z)g(z,y)xy0otherwise\displaystyle{ h \left( x , y \right) = \left\lbrace \begin{array}{ll} \mathop{ \sum }\limits _{ \left\lbrace z : x \preceq z \preceq y \right\rbrace } f \left( x , z \right) g \left( z , y \right) & x \preceq y \\ 0 & \text{otherwise}\quad \end{array} \right. } h=fg\displaystyle{ h = f \ast g } f,gF,\displaystyle{ f , g \in \left\langle \mathscr{ F } , \ast \right\rangle }
  • 封闭?✅
  • 结合率?✅
  • 幺元?e(x,y)={1x=y0otherwise\displaystyle{ e \left( x , y \right) = \left\lbrace \begin{array}{ll} 1 & x = y \\ 0 & \text{otherwise}\quad \end{array} \right. }fF,ef=fe=f\displaystyle{ \forall f \in \mathscr{ F } , e \ast f = f \ast e = f }
  • 全员可逆?