1.2k views

Let S = {1, 2, 3,........, m}, m >3. Let X1.........Xn 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 Xthat 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 | 1.2k views

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
can someone plz explain with an example taking n=4
here we can take m not n because n is number of subset.

take m= 4 {1,2,3,4}

make 3 elemnt subset = {1,2,3} {1,3,4} {2,3,4}, {1,2,4}

n = 4 i.e. number of subset  question said f(i) = number of time i i appear in different set.

so add for each element i.e. f(1) +f(2)+f(3)+f(4) = 3+3+3+3= 12

@manoj how this line comes

f(i) =  (m-1)(m-2)/2 =  m(m-1)(m-2)/2

for 1 element (m-1)(m-2)/2 subsets

for m  "           m (m-1)(m-2)/2 "

but imp part is here mc(m-1)c3

which we can formulate only by taking example

someone plz explain why 3m is not the answer. i is from 1 to m and we are adding 3, m times so it should be 3m.

@vineet

"f(i) is the number of sets Xthat contain the element i" , Here it says number of subsets that contain element 'i' and summation explains total number of subsets that contain that particular element 'i' (f(i)) and  'm' represents elements and 'n' is the number of subsets and each subset size is 3 so ∑f(i) = 3n

For those who are wondering how to calculate

$$f(i)=\binom{m}{3}-\binom{m-1}{3}$$

One way is to expand and simplify and another way is to apply Pascal's triangle

From Pascal's triangle, we know

$$\binom{n}{k-1}+\binom{n}{k}=\binom{n+1}{k}$$

$$or,\binom{n+1}{k}-\binom{n}{k}=\binom{n}{k-1}$$

Applying this formula, we get

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

PS: Well there is an alternative way to find $f(i)$

vineet.ildm you are confused because in Prashant.'s example there were 4 elements and 4 subsets but that's not the case when you take size of S more than 4

if you take S = {1,2,3,4,5}

there will be $\binom{5}{3}$ = 10 subsets of cardinality 3

and 1 will appear in $\binom{4}{2}$ = 6 subsets

and similarly other 4 elements of S making sum = 5 * 6 = 30

which is 3n = 3 * 10 = 30

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
What did you achieve by writing the same content as present in the best answer ?
In terms of Points:  points for ans + 2 upvotes and One nice comment.:)

My ans is 3 line more than the best ans.

I just want to simplify the answer.I think if anyone simplifies the best answer then it is really helpful for aspirants like me.
In many places I saw you just writing answer as "option A" even though best answer has an explanation for option A.

If you are doing it for points then it's pretty much useless.

Alternative way:

$|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$$