Solution: 2018 Fall Midterm - 1

Author: Michiel Smid

Question

Let $n \geq 3$ be an integer and let $S$ be a set consisting of $n$ elements. How many ordered triples $(A, B, C)$ are there for which $A \subseteq S$, $B \subseteq S$, $C \subseteq S$, and $A$, $B$, and $C$ are pairwise disjoint?

(a)

$4^n$

(b)

$3^n$

(c)

$5^n$

(d)

$2^n$

Solution

To determine the number of ordered triples $ (A, B, C) $ such that $ A subseteq S $, $ B subseteq S $, $ C subseteq S $, and $ A $, $ B $, and $ C $ are pairwise disjoint, we start by analyzing the choices available for each element in the set $ S $.

Given $ S $ is a set with $ n $ elements, each element $ x in S $ must belong to one of the sets $ A $, $ B $, $ C $, or to none of these sets. These four choices for each element are:

$ x in A $
$ x in B $
$ x in C $
$ x notin A \cup B \cup C $

Since the elements of $ S $ are independently distributed among these four choices, each element has 4 options. Therefore, for each of the $ n $ elements, there are 4 independent choices.

$ 4 \cdot 4 \cdot 4 \cdot … \cdot 4$

Hence, the total number of ways to assign each of the $ n $ elements to either $ A $, $ B $, $ C $, or none of them is $ 4^n $.

Thus, the total number of ordered triples $ (A, B, C) $ where $ A $, $ B $, and $ C $ are pairwise disjoint subsets of $ S $ is: $ 4^n $

So, the number of such ordered triples is $boxed{4^n}$.