Number of way choose ordered distinct quadruples $(A,B,C,D)$ from $\{1,2,...,n\}(n\geq 2)$

Question

Number of way choose ordered distinct quadruples $(A,B,C,D)$ from $\{1,2,...,n\}(n\geq 2)$ such that $A\subseteq B\cup C\cup D$.

I think in following manner: $\forall x\in \{1,2,...,n\} $ if $A$ included it then it must be in $B \vee C \vee D$ or if $x$ not in $A$ it can be at any $B \vee C \vee D$ such a way give us $7^n$ .Any one can verify my solution?

Answer 1

• We can choose $A$ on $2^n$ ways.
• For each $a\in A$ there must be at least one from $\{B,C,D\}$ which contains $a$. That we can do on $2^3-1 =7$ ways. So if $|A|=k$ then we have $7^k$ options. The rest of $n-k$ elements we can arrange in sets $B,C, D$ arbitrary, so that is $8^{n-k}$ ways.

So we have $$\sum _{k=0}^n{n\choose k}\cdot 7^k\cdot 8^{n-k} = 15^n$$ 4-couples $(A,B,C,D)$.

Answer 2

Let's count the $(A,B,C,D)$ for a given choice of $S=B\cup C\cup D$ (where $k=|S|$).

Draw a Venn diagram for $B,C,D$. We can distribute the elements of $S$ among the $7$ regions, and that corresponds to a choice of $(B,C,D)$. Labelling the regions $1$-$7$, this is the same as a function from $S$ to the set $\{1,\cdots,7\}$, of which there are $7^k$. Also there are $2^k$ choices for $A\subseteq S$.

There are $\binom{n}{k}$ choices for $S\subseteq\{1,\cdots,n\}$, so summing over $k$ we get

$$ \sum_{k=0}^n \binom{n}{k}\cdot7^k\cdot2^k. $$

Do you see why this is $15^n$?