Proving combinatoric identities with the inclusion and exclusion principle

130 Views Asked by At

Let V be a finite set and let the number $a(F) \in\Bbb R$ for $ F \subseteq V$.

We define the numbers

$$b(G, E) = \sum_{E\subseteq F\subseteq G} (-1)^{|G-F|} a(F)$$

where $E\subseteq G\subseteq V$and $b(F) = b(F, \emptyset ) $for $ F \subseteq V$

(a) For fixed $E\subseteq G\subseteq V$ prove that $$a(G) = \sum_{E\subseteq F\subseteq G} b(F, E) $$ (b) Prove that $$b(V, F) =\sum_{(V-E) \subseteq F}b(E) $$ for every $F\subseteq V$

Thoughts: The principle of inclusion and exclusion will be useful.

1

There are 1 best solutions below

0
On

Suppose $a_1,a_2$ are two functions from subsets of $V$ to $\Bbb R$ and $r_1, r_2$ are two real numbers. Let $a_3(F)=r_1a_1(F)+r_2a_2(F)$ for all subsets $F$ of $V$. It is straightforward to verify that if (a) and (b) are true when $a=a_1$ and when $a=a_2$, then they are also true when $a=a_3$.

That means it is enough to prove the simple case when $a=e_T$ for some subset $T$ of $V$, where $e_T(T)=1$ and $e_T(F)=0$ if $F\not=T$. That is, $e_T(F)=[T=F]$, where $[P]$ is the Iverson bracket.

In terms of rudimentary linear algebra, all functions from subsets of $V$ to $\Bbb R$ is a vector space (linear space) over $\Bbb R$ with basis $\{e_T\mid T\subseteq V\}$. Because of the linearity, it is enough to prove (a) and (b) hold for each element in the basis.

Henceforth, let $a=e_T$ for some fixed $T\subseteq V$.

$$b(G, E) = (-1)^{|G-T|}[E\subseteq T\subseteq G] $$


(a) For fixed $E\subseteq G\subseteq V$, $$\begin{aligned} \quad\sum_{E\subseteq F\subseteq G} b(F, E)&=\sum_{E\subseteq F\subseteq G}(-1)^{|F-T|}[E\subseteq T\subseteq F]\\ &=[E\subseteq T]\sum_{T\subseteq F\subseteq G} (-1)^{|F-T|}\\ &=[E\subseteq T][T=G]\\ &=[T=G]\\ &=a(G) \end{aligned}$$ where the third last equality comes from the lemma below.


(b) For fixed $F\subseteq V$, $$\begin{aligned} \sum_{(V-E) \subseteq F}b(E)&=\sum_{(V-E) \subseteq F}(-1)^{|E-T|}[T\subseteq E]\\ &=\sum_{((V-F)\cup T)\subseteq E}(-1)^{|E-T|}\\ &=(-1)^{|V-T|}\sum_{((V-F)\cup T)\subseteq E} (-1)^{|V-E|}\\ &=(-1)^{|V-T|}[((V-F)\cup T)=V]\\ &= (-1)^{|V-T|}[F\subseteq T]\\ &=B(V, F) \end{aligned}$$ where the third last equality comes from the lemma below.


Lemma: For any two finite sets $S\subseteq L$, $\displaystyle\sum_{S\subseteq M\subseteq L}(-1)^{|M-S|}=[S=L]$.

Proof: $$\begin{aligned} \quad\sum_{S\subseteq M\subseteq L} (-1)^{|M-S|}&=\sum_{d=0}^{|L-S|}\sum_{{S\subseteq M\subseteq L}\,\land\, |M-S|=d}(-1)^d\\ (\text{choose the $d$-element set }M\!-\!S)\quad&=\sum_{d=0}^{|L-S|}{|L-S|\choose d}(-1)^d\\ (\text{the binomial theorem})\quad&=(1+(-1))^{|L-S|}=[S=L]\quad\Box\\ \end{aligned}$$


A previous version of this answer proves (a) and (b) more directly.