I'm asked to count the number of functions $f:\{1,2,3,4\} \rightarrow\{1,2,3,4,5\}$ such that $f(1)∉\{f(2),f(3),f(4)\}, f(2)\neq f(3), f(3) \neq f(4)$. How do I make the inclusion-exclusion argument needed to solve this problem?
I'd also like to know how to make a venn diagram with these sets so I can visualize them. Any tips?
On
Let $A_1$ be the functions with $f(2)=f(3)$, $A_2$ be the functions with $f(3)=f(4)$, $A_3$ be the functions with $f(1)\in \{f(2),f(3),f(4)\}$.
Then the count you want is, via inclusion-exclusion:
$$5^4-|A_1\cup A_2\cup A_3| = 5^4-(|A_1|+|A_2|+|A_3| - |A_1\cap A_2|-|A_1\cap A_3|-|A_2\cap A_3| + |A_1\cap A_2\cap A_3|)$$ Then work them out the sized of the various intersections.
The only hard set is $A_3$, which you might want to break into three sets, $B_2,B_3,B_4$, where $B_i$ contains the case when $f(1)=f(i)$. This is going to get messier, because the $B_i$ are not disjoint, however.
Actually, it might be better to write it as $A_{ij}=\{f\mid f(i)=f(j)\}$. Then you want:
$$5^4-|A_{12}\cup A_{13}\cup A_{14}\cup A_{23}\cup A_{34}|$$
Then $|A_{ij}|=5^3$. $|A_{ij}\cap A_{kl}|=5^2$ for any $(i,j)\neq (k,l)$.
The tricky part is when you have three. Then $$|A_{12}\cap A_{23}\cap A_{13}|=|A_{13}\cap A_{14}\cap A_{34}|=5^2$$ but all other trios give $5$, because all four values $f(1),f(2),f(3),f(4)$ are equal.
The rest are all trivially $5$. This gives:
$$5^4 - (5\cdot 5^3 - 10\cdot 5^2 +(2\cdot 5^2+13\cdot 5)-10\cdot 5 + 5)=180$$
Inclusion-exclusion is a little silly here. There are only two possibilities given your constraints: either $f(1), f(2), f(3), f(4)$ are all different, or $f(2) = f(4)$ and the other two ($f(1)$ and $f(3)$) are different.
In the first case, there are 5 ways to pick $f(1)$, 4 ways to pick $f(2)$, 3 ways to pick $f(3)$, and 2 ways to pick $f(4)$, for $5 \cdot 4 \cdot 3 \cdot 2 = 120$ possibilities. Can you find how many possibilities there are in the second case?