Combinatorics: help with the Inclusion-exclusion principle

Question

$A=\{1,2,3,4\}$

$B=\{5,6,7,8,9\}$

$K$ is a relation from $A$ to $B$ ($K\subseteq AXB)$

1. in how many $K$'s - $1 \notin domain(K)$ ?

2. in how many $K$'s - $\{1,2,3\}\subseteq domain(K)$ (use the Inclusion-exclusion principle).

for example, one option is $K =\{(2,5),(2,6),(3,5),(4,9)\}$

$domain(K)=\{2,3,4\}$

---

1. I'm pretty sure it's all the subsets of the set

   $\{(2,5),(2,6),(2,7),(2,8),(2,9),(3,5),(3,6),(3,7),(3,8),(3,9),(4,5),(4,6),(4,7),(4,8),(4,9)\} = 2^{15}=32,768 $

   which is weird because all the subsets of $AXB$ is $2^{20}=1,048,576$ and only $32,768$ of them don't include (1,x) elements?

2. I need help determining what sets I use for the Inclusion-disclusion principle, is it:

   $A_1=$ the set of $\{1,2\} \subseteq domain(K) $

   $A_2=$ the set of $\{1,3\} \subseteq domain(K) $

   $A_3=$ the set of $\{1,4\} \subseteq domain(K) $

   $A_4=$ the set of $\{2,3\} \subseteq domain(K) $

   $A_5=$ the set of $\{2,4\} \subseteq domain(K) $

   $A_6=$ the set of $\{3,4\} \subseteq domain(K) $

Answer 1

1. Looks correct. It's the possible relations from $\{2,3,4\}$ to $\{5,6,7,8,9\}$, of which there are $2^{3 \times 5}$.

2. I think we're meant to use the idea of part 1. here.

   • Include: There are $2^{4 \times 5}$ relations.
   • Exclude: There are $2^{3 \times 5}$ relations that don't contain $1$ in the domain. There are $2^{3 \times 5}$ relations that don't contain $2$ in the domain. There are $2^{3 \times 5}$ relations that don't contain $3$ in the domain.
   • Include: There are $2^{2 \times 5}$ relations that don't contain $1$ and $2$ in the domain. There are $2^{2 \times 5}$ relations that don't contain $1$ and $3$ in the domain. There are $2^{2 \times 5}$ relations that don't contain $2$ and $3$ in the domain.
   • Exclude: There are $2^{1 \times 5}$ relations that don't contain $1$, $2$ and $3$ in the domain.