公考容斥原理的极值问题_行测容斥原理极值公式

容斥极值公式怎么来的？

容斥原理是一种计数原理，用于计算满足某些条件的元素的数量。容斥极值公式是容斥原理的一种特殊情况，用于计算两个集合的交集和并集的最大值和最小值。

容斥极值公式的推导过程如下：

假设有两个集合A和B，它们的元素个数分别为m和n。我们要计算A\cap B的最大值和最小值。

我们可以使用容斥原理来计算A\cap B的元素个数。容斥原理的基本思想是，先将两个集合的元素个数相加，然后减去它们的交集元素个数，再加上它们的并集元素个数。

具体地，我们可以将A和B的元素个数相加，得到：

m+n

然后，我们减去A\cap B的元素个数，得到：

m+n-A\cap B

最后，我们加上A\cup B的元素个数，得到：

m+n-A\cap B+A\cup B

由于A\cup B包含了A\cap B，因此我们可以将上面的式子化简为：

这就是A\cap B的元素个数的计算公式。

接下来，我们要计算A\cap B的最大值和最小值。我们可以通过对上面的式子进行变形来得到。

首先，我们可以将m+n看作一个常数，记为c。这样，上面的式子就可以写成：

c-A\cap B

我们可以看到，A\cap B的最大值就是c，即：

\max(A\cap B)=c

接下来，我们考虑A\cap B的最小值。由于A\cap B的元素个数不能为负数，因此A\cap B的最小值为0，即：

\min(A\cap B)=0

综上所述，容斥极值公式为：

\max(A\cap B)=m+n

\min(A\cap B)=0

容斥极值公式推导过程？

容斥极值公式指的是一个集合的多个子集合中，能够满足条件的元素数量的最大或最小值问题。该公式的推导过程如下：

假设我们有若干个集合 $A_1, A_2, \cdots, A_n$，它们的元素数量分别为 $|A_1|, |A_2|, \cdots, |A_n|$。我们要在这些集合里面选择一定数量的元素，使得这些元素同时属于某些集合。我们设符合条件的元素数量为 $N$，那么 $N$ 的取值范围是 $\max(0, N_{\min}) \leq N \leq \min(|A_1|, |A_2|, \cdots, |A_n|, N_{\max})$，其中 $N_{\min}$ 和 $N_{\max}$ 分别表示符合条件的元素数量下限和上限。

我们可以对这个问题应用容斥原理来求解。容斥原理指的是，如果我们要计算几个集合的交集的元素数量，可以把这些集合的元素数量相加，然后减去它们的两两交集的元素数量，再加上它们的三个交集的元素数量，最后减去它们的四个交集的元素数量，以此类推。具体地，我们有：

$$ N = \sum_{i=1}^n (-1)^{i+1} \sum_{1 \leq j_1 < j_2 < \cdots < j_i \leq n} |A_{j_1} \cap A_{j_2} \cap \cdots \cap A_{j_i}| $$

其中 $|A_{j_1} \cap A_{j_2} \cap \cdots \cap A_{j_i}|$ 表示集合 $A_{j_1}, A_{j_2}, \cdots, A_{j_i}$ 的交集的元素数量。我们可以把 $N$ 表示成所有交集元素数量的和。

然后我们要把这个式子转化成一个更简单的形式。设 $S_k$ 表示集合 $A_1, A_2, \cdots, A_k$ 中任意 $k$ 个的交集的元素数量。即，

$$ S_k = \sum_{1 \leq j_1 < j_2 < \cdots < j_k \leq n} |A_{j_1} \cap A_{j_2} \cap \cdots \cap A_{j_k}| $$

注意到 $S_k$ 是 $S_{k-1}$ 的一个子集，因为任意 $k$ 个集合的交集可以被分解成其中任意 $k-1$ 个集合的交集和另外一个集合的交集。于是我们有 $S_{k-1} \subseteq S_k$。因此，上面的式子可以被改写为：

$$ N = \sum_{k=1}^n (-1)^{k+1} \binom{n}{k} S_k $$

这个式子指的是，在 $n$ 个集合中任意选择 $k$ 个集合的交集的元素数量为 $(-1)^{k+1} \binom{n}{k}$，其中 $\binom{n}{k}$ 表示从 $n$ 个集合中任意选择 $k$ 个集合的组合数；然后把所有选择方式的元素数量相加即可。

接下来，我们可以使用这个式子求解最大值和最小值问题。如果要求 $N$ 的最大值，我们对于每一个 $k$，选择 $S_k$ 的最大值，并且将其相加，因为 $S_k$ 是 $S_{k-1}$ 的子集，所以我们在选择 $S_k$ 的时候，会同时选择 $S_{k-1}$ 中的元素。因此，我们需要

多集合容斥极值原理？

集合容斥极值问包括多个集合，但集合之间的相互关系并不明确。

(1)集合之间没有任何交叉时，这些集合的元素总数最多。

(2)当一个集合包含另一个集合时，这两个集合的元素总数最少。

设全体的数量为m，全体之下的集合分别为A、B、C、D…并用a、b、c、d…表示每个集合的数量，则有：

A∩B的最小值=a+b-m

A∩B∩C的最小值=a+b+c-2m

A∩B∩c∩D的最小值=a+b+c+d-3m

中公点评：多个集合的最小值可依此类推，依照上面公式进行计算。