Let $S=\{1,2,\cdots, n\}$ and let $T$ be the set of all ordered triples of subsets of $S$, 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|\]
Problem
Source: RMO (Mumbai Region) 2015 P6
Tags: combinatorics, combinatorics proposed, Enumerative Combinatorics, counting
libra8
06.12.2015 15:48
$7^n$ . suppose one such intersection is k. then those k elements are present in each of the 3 subsets. the rest of the elements have 6 choices each. sum over.
TheOneYouWant
09.12.2015 15:22
Hi - sorry for any LaTeX issues if any, i have just started to learn First of all, i believe the answer is not $7^n$ but $n.7^{n-1}$ Here is my procedure:
Consider the Venn diagram of $A1, A2$ and $A3$.
You Have 7 choices other than $U$-$A1\cup$$A2\cup$$A3$.
Let there be $r$ objects in $A1\cap$$A2\cap$$A3$
Then we have ${n\choose r}$ ways of choosing those $r$ and $6^{n-r}$ choices for the rest.
Also, since we want the summations of the intersections we need to multiply no. of cases with $r$ objects in $A1\bigcap$$A2\bigcap$$A3$ $r$ times.
Thus, the expression is $\displaystyle\sum\limits_{r=0}^n r.6^{n-r}.{n\choose r}$
which by Newton's relation and binomial coefficients is $n.7^{n-1}$
libra8
09.12.2015 17:28
why multiply it with r?
TheOneYouWant
09.12.2015 19:38
Since we need to multiply the sets with their respective weights in $A_1\cap$$A_2\cap$$A_3$.. See, the problem is summation of no. of elements in the intersection, hence we need to multiply with no. of elements in intersection. For example, take $n=1$. For this, there is only one intersection when $A_1,A_2,A_3 = S$
moving_points_kid
25.01.2020 06:37
A bit too late but here is a nice overkill solution:
We employ probabilistic method.Let $X$ be the random variable corresponding to the number of elements in $A_1\cap A_2\cap A_3$.
Also let $X_i$ be the indicator variable which is $1$ if $i \in A_1\cap A_2\cap A_3$ or $0$ otherwise.So $$X=X_1+X_2+ \cdots +X_n$$So by the linearity of expectation $\mathbb{E}[X]=\mathbb{E}[X_1]+\mathbb{E}[X_2]+\cdots+\mathbb{E}[X_n]$.Now its obvious that $\mathbb{E}[X_i]=\tfrac{1}{7}$ for each $i$.Hence $\mathbb{E}[X]=\tfrac{n}{7}$.But $\mathbb{E}[X]=\tfrac{S}{7^n}$ by the definition where \[S= \sum_{(A_1,A_2,A_3)\in T}|A_1\cap A_2\cap A_3|\]So $S=n \cdot 7^{n-1}$ as desired.
math_and_me
25.01.2020 06:46
https://www.google.com/url?sa=t&source=web&rct=j&url=https://olympiads.hbcse.tifr.res.in/olympiads/wp-content/uploads/2016/09/sol-crmo15-5.pdf&ved=2ahUKEwiuocuu653nAhVSILcAHYJZCGEQFjAAegQIAhAB&usg=AOvVaw1wK8Pydh8BKoDRsRo358FC
yunxiao
27.01.2020 15:35
obviously we can use probability theory