1.8k views

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 | 1.8k views

$|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$$
answered by Junior (901 points)
selected by
0
nice explaination !!
0

No.of three elements subset = n= mC3

Assuming that X1, X2, ... Xn are all  the subsets of S

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

answered by Active (2.4k points)
edited by
0
can someone plz explain with an example taking n=4
+21
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
0

@manoj how this line comes

f(i) =  (m-1)(m-2)/2 =  m(m-1)(m-2)/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

+1
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.
0

@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

+2

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

0

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

0

@Mk Utkarsh yes this is one of the problem when we try to take an example and solve.

https://gateoverflow.in/2083/gate2014-3-49 like this question. Answer changes according to cardinality of the set.

But with practice you can overcome this by satisfying the criteria in question like:

1: m>3

2: getting conflict when m and n =4 as both a,b results in 12.

3 : go with m =5 and you can eliminate options.

Though it looks lengthy, it won't take much time and you will be sure about answer. :)

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 Loyal (7.1k points)
edited by
+3
What did you achieve by writing the same content as present in the best answer ?
+1
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.
+5
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.

1
2