Skip to content
Notes

第六章 容斥原理

容斥原理

计数 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 } } 的对象组成的子集，则

∣A‾1∩A‾2∣=∣S∣−∣A1∣−∣A2∣+∣A1∩A2∣\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| }

推广一下

∣A‾1∩A‾2∩…A‾m∣=∣S∣−∑∣Ai∣+∑∣Ai∩Aj∣−…+(−1)m∑∣A1∩A2∩…∩Am∣\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 } } 之一的对象个数

∣A1∪A2∪…∪Am∣=∑∣Ai∣−∑∣Ai∩Aj∣+∑∣Ai∩Aj∩Ak∣−…+(−1)m+1∑∣A1∩A2∩…∩Am∣\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=125∣A1∩A2∣=1000lcm⁡(5,6)=33∣A1∩A3∣=1000lcm⁡(5,8)=25∣A2∩A3∣=1000lcm⁡(6,8)=100024=41∣A1∩A2∩A3∣=1000lcm⁡(5,6,8)=1000120=8∣A‾1∩A‾2∩A‾3∣=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+k−1r)\displaystyle{ { r + k - 1 \choose r } }

确定多重集合 T={3⋅a,4⋅b,5⋅c}\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+3−16)\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 } 中任意选择，即得到上面的式子

∣A‾1∩A‾2∩A‾3∣=∣S∣−(∣A1∣+∣A2∣+∣A3∣)+(∣A1∩A2∣+∣A1∩A3∣+∣A2∩A3∣)−∣A1∩A2∩A3∣=(10+3−110)−((6+3−16)+(5+3−15)+(4+3−14))+((1+3−11)+(0+3−10)+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!(1−11!+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∣=(n−1)!\displaystyle{ \left| A _{ 1 } \right| = \left| A _{ j } \right| = {\left( n - 1 \right) !} }
  • ∣A1∩A2∣=∣Ai∩Aj∣=(n−2)!\displaystyle{ \left| A _{ 1 } \cap A _{ 2 } \right| = \left| A _{ i } \cap A _{ j } \right| = {\left( n - 2 \right) !} }
  • …
  • ∣A1∩A2∩…∩Ak∣=(n−k)!\displaystyle{ \left| A _{ 1 } \cap A _{ 2 } \cap \ldots \cap A _{ k } \right| = {\left( n - k \right) !} }
Dn=∣A‾1∩A‾2∩…A‾n∣=n!−(n1)(n−1)!+(n2)(n−2)!−…+(−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=(n−1)(Dn−1+Dn−2)\displaystyle{ D _{ n } = \left( n - 1 \right) \left( D _{ n - 1 } + D _{ n - 2 } \right) } Dn=nDn−1+(−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 } 的所有排列 i1i2…in\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 个非攻击型不可区分的车放到带有禁止放置位置的 n 行 n 列棋盘上的放置方法数等于

n!−r1(n−1)!+r2(n−2)!−…+(−1)krk(n−k)!+…+(−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 个非攻击型车在 n 行 n 列棋盘上的所有放置方法的集合
  • Pj\displaystyle{ P _{ j } }: 在第 j 行上的车是在属于 Xj\displaystyle{ X _{ j } } 的列上
  • ∣A1∣=∣X1∣(n−1)!,∣Ai∣=∣Xi∣(n−1)!\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(n−1)!\displaystyle{ \Sigma \left| A _{ i } \right| = r _{ 1 } {\left( n - 1 \right) !} }，r1\displaystyle{ r _{ 1 } } 等于棋盘上禁止放车的格子数
  • Σ∣Ai∩Aj∣=r2(n−2)!\displaystyle{ \Sigma \left| A _{ i } \cap A _{ j } \right| = r _{ 2 } {\left( n - 2 \right) !} }，r2\displaystyle{ r _{ 2 } } 等于把两个非攻击型车放到棋盘禁止位置上的方法数
  • Σ∣Ai1∩Ai2∩…∩Aik∣=rk(n−k)!\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∣=(n−1)!\displaystyle{ \left| A _{ 1 } \right| = \left| A _{ j } \right| = {\left( n - 1 \right) !} }
  • ∣A1∩A2∣=∣Ai∩Aj∣=(n−2)!\displaystyle{ \left| A _{ 1 } \cap A _{ 2 } \right| = \left| A _{ i } \cap A _{ j } \right| = {\left( n - 2 \right) !} }
  • Qn=∣A‾1∩A‾2∩…∩A‾m∣=Dn+Dn−1\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)=∑L⊆KF(L)\displaystyle{ G \left( K \right) = \sum _{ L \subseteq K } F \left( L \right) }，K⊆Xn\displaystyle{ K \subseteq X _{ n } }
  • 莫比乌斯反演可将上式反解 F(K)=∑L⊆K(−1)∣K∣−∣L∣G(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 > } H⊆G,H≠∅,<H,∘> is Group\displaystyle{ H \subseteq G , H \ne \varnothing , < H , \circ > \text{ is Group} }

判定定理

设 G\displaystyle{ G } 是群，H⊆G,H≠∅\displaystyle{ H \subseteq G , H \ne \varnothing }，H\displaystyle{ H } 是 G\displaystyle{ G } 的子群当且仅当 ∀x,y∈H,xy−1∈H\displaystyle{ \forall x , y \in H , x y ^{ {-1 } } \in H }

充分性：设 G\displaystyle{ G } 是群，H⊆G,H≠∅\displaystyle{ H \subseteq G , H \ne \varnothing }，H\displaystyle{ H } 是 G\displaystyle{ G } 的子群

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

必要性

F(X)={f:X×X→R∣∀x,y∈X,x⪯y→f(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:x⪯z⪯y}f(x,z)g(z,y)x⪯y0otherwise\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=f∗g\displaystyle{ h = f \ast g } f,g∈⟨F,∗⟩\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. }，∀f∈F,e∗f=f∗e=f\displaystyle{ \forall f \in \mathscr{ F } , e \ast f = f \ast e = f }
  • 全员可逆？