The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+34 votes

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
asked in Set Theory & Algebra by Loyal (4.3k points)
edited by | 1.2k views

3 Answers

+43 votes
Best answer
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.$
answered by Loyal (2.8k points)
edited by
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.


"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


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

From Pascal's triangle, we know




Applying this formula, we get



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

+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

answered by Veteran (16.3k points)
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.
+2 votes

Alternative way:


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


answered by Junior (719 points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,687 questions
40,231 answers
38,803 users