
6. Let $S=\{1,2, \ldots, n\}$ and let $T$ be the set of all ordered triples of subsets of $S$, say $\left(A_{1}, A_{2}, A_{3}\right)$, such that $A_{1} \cup A_{2} \cup A_{3}=S$. Determine, in terms of $n$,

$$
\sum_{\left(A_{1}, A_{2}, A_{3}\right) \in T}\left|A_{1} \cap A_{2} \cap A_{3}\right|
$$

where $|X|$ denotes the number of elements in the set $X$. (For example, if $S=\{1,2,3\}$ and $A_{1}=\{1,2\}, A_{2}=\{2,3\}, A_{3}=\{3\}$ then one of the elements of $T$ is $(\{1,2\},\{2,3\},\{3\})$.)


## Solution 1

Let $X=\left(A_{1}, A_{2}, A_{3}\right) \in T$ and let $i \in A_{1} \cap A_{2} \cap A_{3}$. The number of times the element $i$ occurs in the required sum is equal to the number of ordered tuples $\left(A_{1}-\{i\}, A_{2}-\{i\}, A_{3}-\{i\}\right)$ such that

$$
A_{1}-\{i\} \cup A_{2}-\{i\} \cup A_{3}-\{i\}=S-\{i\}
$$

For every element of $S-\{i\}$, there are eight possibilities - whether the element belongs to or does not belong to $A_{i}$ for $i=1,2,3$. Out of these the case when the element does not belong to any of the three subsets violates $(*)$. Therefore, each element can satisfy the requirement in 7 ways. The number of tuples is, therefore, $7^{n-1}$ and the sum is $n \cdot 7^{n-1}$.

