The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+38 votes
1.6k 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$
asked in Set Theory & Algebra by Active (3.7k points)
edited by | 1.6k views

3 Answers

+11 votes
Best answer
$|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 (867 points)
selected by
0
nice explaination !!
+47 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.$

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

+1

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

+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 Loyal (6.8k 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.


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

40,992 questions
47,620 answers
146,891 comments
62,346 users