Counting number of way to choose ordered distinct quadruples
$(A,B,C,D)\subseteq\{1,2,…,n\}(n\geq 2)$ with additional condition $A\cap B\subseteq C\cup D$.
In order to solve this problem,i set length of $|A\cap B|=k$ then distribute those $k$ elements in $3$ region of Venn diagram of $B\cup C$ and i can do this in $3^k$ different way and we have $\binom{n}{k}$ choice for select those $k$ elements.
At the last step for remaining $n-k$ we have $7^{n-k}$ choice,because for each $n-k$ elements we can push it in $A $ or $B$ (not in intersect region) and $4$ why for push it in $C$ or $D$. Summing over all we have:
$\sum_{k=0}^{n}\binom{n}{k}3^k 7^{n-k}=10^n$
But i think my solution is not true!.Any one can help me?
Best Answer
For any $x \in \{1,2,\ldots,n\}$ there are $16 = 2 \cdot 2 \cdot 2 \cdot 2$ cases:
However, due to the additional condition $A \cap B \subseteq C \cup D$, we cannot have $x \in A \land x \in B \land x \notin C \land x \notin D$. Therefore the $16$ cases are reduced to $15$ and considering all elements we have $15^n$ ordered distinct quadruples (where any two sets can be equal).
The result agrees with your reasoning once that you correct it replacing $7 = 3 + 4$ ($3$ for $A, B$ and $4$ for $C, D$) with $12 = 3 \cdot 4$.