edited by
10,906 views
76 votes
76 votes

Let $S = \{1, 2, 3,\ldots, m\}, m >3.$ Let $X_1,\ldots,X_n$ be subsets of $S$ each of size $3.$ Define a function $f$ from $S$ to the set of natural numbers as, $f(i)$ is the number of sets $X_j$ that contain the element $i.$ That is $f(i)=\left | \left\{j \mid i\in X_j \right\} \right|$   then $ \sum_{i=1}^{m} f(i)$ is:

  1. $3m$
  2. $3n$
  3. $2m+1$
  4. $2n+1$
edited by

9 Answers

Best answer
58 votes
58 votes
$|S|=m$

No. of three elements subset $=n=\binom{m}{3}$

Function $f(i)$ is defined as No. of three elements subset which contain element $i$.

Without loss of generality, lets assume $i=1$

Now we need to count three elements subset which contain element $1$.
All those subset will be of the form $\left \{ 1,a,b \right \}$, where $a$ and $b$ are distinct and not equal to $1$.

We can choose all those $a$ and $b$ in $\binom{m-1}{2}$ ways

So, $f(1)=\binom{m-1}{2}$, which is true for any $i$
Therefore, $f(i)=\binom{m-1}{2}$

Now, $$\sum_{i=1}^{m}f(i)=\sum_{i=1}^{m}\binom{m-1}{2}$$
$$=m\binom{m-1}{2}=3\binom{m}{3}=3n$$

Correct Answer: $B$
edited by
78 votes
78 votes

Alternative Approach:

Total elements in $S = m$

Total number of subsets of size $3$ each can be $^{m}c_{3}.$

Now suppose take $1^{st}$ element $1.$ Out of $^{m}c_{3}$ subsets $1$ wont be there in $^{(m-1)}c_{3}$ subsets.

So $1$ will be there in $^{m}c_{3} - ^{(m-1)}c_{3} =\frac{(m-1)(m-2)}{2}$ subsets.

$\sum f(i) =\sum \frac {(m-1)(m-2)}{2} =\frac {m(m-1)(m-2)}{2}.$

We know, $^{m}c_{3} = n$ (No. of $X$ subset)     $\therefore \frac {m(m-1)(m-2)}{2} = 3n.$

edited by
5 votes
5 votes

Number of subsets of size 3 from m elements$\Rightarrow$$m\choose 3$$=n\ \ ....(1)$

$f(i$) is the number of sets $X_{j}$ that contain the element i.

$f(1)=$Number of subsets which contain 1$=$$m-1\choose 2$

$\sum_{i=1}^{m}f(i)=f(1)+f(2)+.......+f(m)=$ $m-1\choose 2$ +$m-1\choose 2$+$m-1\choose 2$+......+$m-1\choose 2$

$m\times$ $m-1\choose 2$ $=m\times \frac{(m-1)(m-2)}{2}=$ $\frac{m(m-1)(m-2)}{2}$


From $(1)$

$\frac{m(m-1)(m-2)}{3\times 2}=n$

$\frac{m(m-1)(m-2)}{2}$ $=3n$

Correct Answer: B

2 votes
2 votes

Given that,  S = {1, 2, 3,........, m}, m >3

Total number of elements in S = m

Total number of subsets of size 3 each can be mc3.

Now suppose take 1st element 1. Out of mc3  subsets  1 wont be there in (m-1)csubsets.

So 1 will be there in mc(m-1)c= (m-1)⨉(m-2)/2 subsets. 

Similiarly for all remaining elements 2,3,4,5....m, we have same number of subsets.

i.e. mc(m-1)c= (m-1)⨉(m-2)/2

 (from i=1 to m ) ∑f(i) =  (from i=1 to m ) ∑(m-1)⨉(m-2)/2 =  m⨉(m-1)⨉(m-2)/2

In Qs given that  mc= n  (No of X subset) ,    therefore m ⨉ (m-1) ⨉ (m-2)/2 = 3n 

The correct answer is,(B) 3n

edited by
Answer:

Related questions

36 votes
36 votes
4 answers
1
Rucha Shelke asked Sep 16, 2014
7,007 views
Let $X,Y,Z$ be sets of sizes $x, y$ and $z$ respectively. Let $W = X \times Y$ and $E$ be the set of all subsets of $W$. The number of functions from $Z$ to $E$ is$z^{2^{...
25 votes
25 votes
7 answers
3
Rucha Shelke asked Sep 17, 2014
6,468 views
Let $E, F$ and $G$ be finite sets. Let$X = (E ∩ F) - (F ∩ G)$ and$Y = (E - (E ∩ G)) - (E - F)$.Which one of the following is true?$X ⊂ Y$$X ⊃ Y$$X = Y$$X - Y �...
33 votes
33 votes
5 answers
4