Paper 4, Section II, E

Numbers and Sets | Part IA, 2009

(a) State and prove the inclusion-exclusion formula.

(b) Let kk and mm be positive integers, let n=kmn=k m, let A1,,AkA_{1}, \ldots, A_{k} be disjoint sets of size mm, and let A=A1AkA=A_{1} \cup \ldots \cup A_{k}. Let B\mathcal{B} be the collection of all subsets BAB \subset A with the following two properties:

(i) B=k|B|=k;

(ii) there is at least one ii such that BAi=3\left|B \cap A_{i}\right|=3.

Prove that the number of sets in B\mathcal{B} is given by the formula

r=1k/3(1)r1(kr)(m3)r(nrmk3r)\sum_{r=1}^{\lfloor k / 3\rfloor}(-1)^{r-1}\left(\begin{array}{c} k \\ r \end{array}\right)\left(\begin{array}{c} m \\ 3 \end{array}\right)^{r}\left(\begin{array}{c} n-r m \\ k-3 r \end{array}\right)

Typos? Please submit corrections to this page on GitHub.