# Let S = {1, 2, …, n} and let T be the set of all ordered triples of subsets, say $(A_1, A_2, A_3)$ , such that $A_1 \cup A_2 \cup A_3 = S$. Determine, in terms of n, $\sum_{(A_1, A_2, A_3) \in T} |A_1 \cap A_2 \cap A_3 |$, 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}).)

mycroft holmes
272 Points
8 years ago
Suppose we count all triplets A1, A2, A3 that have exactly r elements in common.

The number of ways such triplets can be formed is counted as:
(i) we can choose the r>0 elements to be chosen in nCr ways. Now, the remaining (n-r) elements have each the following choices
(a) they can be part of exactly one set in 3 ways
(b) they can be part of exactly two sets in 3 ways
making available 6 choices for each element
Hence number of such triplets is nCr 6n-r. for r>0

So the required sum is

This is a regular sum that can be obtained by differentiating (x+6)n and putting x=1