# Combinatorics: help with the Inclusion-exclusion principle

$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)$

• I think I got it wrong for 2, should be $A_1 =$ the set of 1 is not in domain K. $A_2 =$ the set of 2 is not in domain K. and $A_3 =$ the set of 3 is not in domain K. right? – Seth Keno May 25 '14 at 1:32

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.
• I think you are right Rebecca, are you sure it's not (total number of K's) - ($S_1 - S_2+S_3$)? or is it the same thing as your answer?, it's just what I've been told in this thread math.stackexchange.com/questions/805059/…, and I want to understand it ;) – Seth Keno May 25 '14 at 2:01
• ok I checked it, it's the same thing ;) – Seth Keno May 25 '14 at 2:05