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

binomial theoremcombinatoricsdiscrete mathematicselementary-set-theory

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?

Best Answer

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

Related Question