I'm trying to tackle the following question, but got no clue how to do so (I know it is not very popular not showing any effort, but this time I really don't know what to do).
Iv'e seen a solution that used inclusion-exclusion, but it seems to be incorrect and I don't understand how it is related to inclusion-exclusion.
Find the number of ordered quadruples $(A,B,C,D)$ where $A,B,C,D$ are sets included in $\{1,2,...,n\}$ such that $A \cup B \cup C \cup D=\{1,2,...,n\}$
Please explain any reasoning of solution, thanks!
Here's a solution that doesn't use inclusion-exclusion:
Each element $i\in\{1,2,\dots,n\}$ must be in at least one of the sets $A$, $B$, $C$, $D$. Thus we may choose any nonempty subset of $\{A,B,C,D\}$ for which $i$ is an element of the chosen sets. There are $15$ ways to do this since there are $15$ nonempty subsets of $\{A,B,C,D\}$. Since we have to do this for $i=1,2,\dots,n$, there are $15^n$ ways to complete the process.
[By the way, I think this should be the same as the inclusion-exclusion solution to this problem, which I believe is $2^{4n}-{n\choose 1}2^{4(n-1)}+{n\choose2}2^{4(n-2)}-...=(16-1)^n$ by the binomial theorem.]