容斥原理与鸽巢原理

hbghlyj

特殊问题
1）棋盘多项式： 记𝑘颗棋子布到𝐶上的方案数为𝑟_𝑘(𝐶)，记𝑅(𝐶) = ∑^𝑛_𝑘=1 𝑟_𝑘(𝐶)
注意递推公式𝑅(𝐶) = 𝑥𝑅(𝐶_(𝑖)) + 𝑅(𝐶_(𝑒))
2）有禁区排列： 记𝑘颗棋子布到禁区的方案数为𝑟_𝑘，则总方案数为𝑛! − 𝑟₁(𝑛 − 1)! + ⋯ + 𝑟_𝑛
3）Ramsey 数： R(𝑎, 𝑏)表示至少有𝑎阶红完全子图或𝑏阶蓝完全子图的顶点数最小值
上界：R(𝑎, 𝑏) ≤ R(𝑎 − 1, 𝑏) + R(𝑎, 𝑏 − 1)
如果右侧两个都是偶数可以减一
R(𝑎, 𝑏) ≤ 𝐶(𝑎 + 𝑏 − 2, 𝑎 − 1) = 𝐶(𝑎 + 𝑏 − 2, 𝑏 − 1)

hbghlyj

棋盘多项式
定理
设$ {r_{i}} $为 $i$ 个棋子布入禁区的方案数，$i=1,2,3,…,n$。有禁区的布子方案数（即禁区内不布棋子的方案数）为 $ {n!}-{r_{1}}{(n-1)!}+{r_{2}}{(n-2)!}-...+{(-1)^{n}}{r_{n}} $

证明
设事件$ A_{i} $为棋子$ i $落入禁区且其余棋子不限定是否落入禁区。那么布子方案数为$ |{\overline {A_{1}}}\cap {\overline {A_{2}}}\cap {\overline {A_{3}}}\cap \cdots \cap {\overline {A_{n}}}| $。该排列数可以用容斥原理求解。在棋盘上的不受限排列数为$ n! $，那么有\begin{aligned}|{\overline {A_{1}}}\cap {\overline {A_{2}}}\cap {\overline {A_{3}}}\cap \cdots \cap {\overline {A_{n}}}|=&|{\overline {A_{1}\cup A_{2}\cup A_{3}\cup \cdots \cup A_{n}}}|\\=&n!-|A_{1}\cup A_{2}\cup A_{3}\cup \cdots \cup A_{n}|\\=&n!-(\sum _{i=1}^{n}|A_{i}|-\sum _{i=1}^{n}\sum _{j>i}|A_{i}\cap A_{j}|+\sum _{i=1}^{n}\sum _{j>i}\sum _{k>j}|A_{i}\cap A_{j}\cap A_{k}|+\cdots +(-1)^{n-1}|A_{1}\cap A_{2}\cap \cdots \cap A_{n}|)\end{aligned}其中，至少有一个棋子落入禁区的方案数为$ \sum _{i=1}^{n}|A_{i}|={r_{1}}(n-1)! $，至少两个棋子落入进去的方案数为$ |\sum _{i=1}^{n}\sum _{j>i}A_{i}\cap A_{j}|={r_{2}}(n-2)! $，以此类推，可以得到等式 $ |{\overline {A_{1}}}\cap {\overline {A_{2}}}\cap {\overline {A_{3}}}\cap \cdots \cap {\overline {A_{n}}}|={n!}-{r_{1}}{(n-1)!}+{r_{2}}{(n-2)!}-...+{(-1)^{n}}{r_{n}} $

例 1.如下图所示，在$ 4\times 4 $的棋盘上，打叉的地方为禁区，求棋子无一落入禁区的排列数。

		×
×			×
	×		×
	×

首先通过排列多项式的性质得到禁区的棋盘多项式为$ 1+6x+11x^{2}+7x^{3}+x^{4} $。 这样，该棋盘在受限情况下的方案数为$ 4!-6\times 3!+11\times 2!-7\times 1!+1=4 $。

例 2.错排问题，即$ n $个元素组成的排列中标号为$ i $的元素不排在第$ i $位的方案数。

该问题即为受限排列问题。 具体到棋盘中，即为在$ n\times n $的棋盘上，所有的对角线元素都是禁区。 对于禁区的棋盘多项式的计算，由于该棋盘中所有元素均不在同一行同一列，根据棋盘多项式的性质容易得到为$ (1+x)^{n} $。 那么，根据受限排列的性质，得到错排方案数为$ n!-C(n,1)(n-1)!+C(n,2)(n-2)!+\cdots +(-1)^{n-1}C(n,n) $。