Counting number of way to choose ordered distinct quadruples $(A,B,C,D)\subseteq\{1,2,…,n\}(n\geq 2)$

combinatoricsdiscrete mathematics

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:

  • $2$ cases for $A$: $x \in A$ or $x \notin A$;
  • $2$ cases for $B$: $x \in B$ or $x \notin B$;
  • $2$ cases for $C$: $x \in C$ or $x \notin C$;
  • $2$ cases for $D$: $x \in D$ or $x \notin D$;

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

Related Question