Do the terms of an inclusion-exclusion summation decrease?

Question

If $|A_1 \cup A_2 \cup \ldots \cup A_n| = c_1 - c_2 + \ldots + (-1)^n c_n$,

where $c_i$ is the sum of the sizes of all of the intersections of $i$ sets at a time (inclusion-exclusion principle);

i.e

$c_1 = |A_1| + |A_2| + \ldots + |A_n|$,

$c_2 = |A_1 \cap A_2| + |A_1 \cap A_3| + |A_2 \cap A_3| + \ldots + |A_{n-1} \cap A_n|$

$\vdots$

$c_n = |A_1 \cap A_2 \cap \ldots \cap A_n|$;

is it guaranteed that $c_1, c_2, \ldots c_n$ is decreasing?

Otherwise, are there any notable circumstances where $c_1, c_2, \ldots, c_n$ is decreasing?

Answer 1

This is just an answer for those who are curious, and it's the best I can do.

If $A_1 = A_2 = \ldots = A_n$

then

$c_1 = \binom{n}{1} \times |A_1|$

$c_2 = \binom{n}{2} \times |A_1|$

$\vdots$

$c_n = \binom{n}{n} \times |A_1|$

so $c_1, c_2, \ldots, c_n$ is not a decreasing sequence, as the binomial sequence is not a decreasing sequence.

Otherwise if $A_1 \neq A_2 \neq \ldots \neq A_n$

Then, for any element in $A_1 \cap A_2$, there's at least two copies of it in $A_1 + A_2$, so it appears as though $c_1 \geq 2 c_2$ if the elements of $ \{ A_i \cap A_j : 1\leq i<j\leq n \}$ are all disjoint. This argument can be extended to say that $c_1 \geq n c_n$ is guaranteed. And even $c_{n-1} \geq n c_n$ is guaranteed because each element of the $n$-intersection is an element of $n$ amount of $(n-1)$-intersections. But a much weaker statement also follows: that $c_{n-2} \geq \frac{n-1}{n} c_{n-1}$ because despite each element of a $(n-1)$-intersection being elements of $n-1$ amount of $(n-2)$-intersections, there are at least $n$ copies of each element amongst all of the $(n-1)$-intersections, and those elements will not be included $n$ times in each $(n-2)$-intersection.

The takeaway from this line of reasoning I belive, is that $c_{k-2} \geq c_{k-1}$ iff there are at least $\frac{1}{k}$ elements in the $(k-2)$-intersections which are not elements of any $(k-1)$-intersection. Furthermore the sequence $c_1, c_2, \ldots, c_n$ is only decreasing if this is true for all relevant $k$.

Answer 2

The inclusion exclusion series involves $(n+1)$ terms.
The magnitude (i.e. absolute value) of the $k$-th term ($k \in \{0,1,2,\cdots,n\}$) represents the sum of $~\displaystyle \binom{n}{k}~$ sub-terms.

There is no general rule governing the relative magnitudes of the first half of the terms. This is because, for $k < (n/2)$ as $k$ goes to $k+1$:

• The size of each sub-term is non-increasing.
  For example, as $k$ goes from $(k=2)$ to $(k=3)$, the sub-terms change from representing expressions like $|S_1 \cap S_2|$ to expressions like $|S_1 \cap S_2 \cap S_3|.$

• The number of sub-terms is increasing.
  For example, assuming that $n > 5$, as $k$ goes from $(k=2)$ to $(k=3)$, the number of sub-terms increases from $~\displaystyle \binom{n}{2}~$ to $~\displaystyle \binom{n}{3}.$

---

On the back half of the group of $(k+1)$ terms, the terms must be decreasing. This is because:

• The first bulletpoint above continues to apply, so the magnitude of the sub-terms can not be increasing.

• Under the assumption that $k > (n/2)$, the number of sub-terms is no longer increasing. Instead, the number of sub-terms is decreasing. The clearest visualization of this is to compare the LHS and RHS of Pascal's Triangle.