Combinatorics

Question

The answer given is ^n-k+1C₂ but couldn't understand how both are related

Answer 1

Ok, the problem is just observation,

K friends are unknown two each other, means any two person from K are not connected ( not even directly or indirectly )

So it means,  graph is divided into K number of components   and each component may have that one person out of K

and each component may have any number of person + one person out of K.

And for any particular component all person involved in that component are friends either connected with direct edges or connected indirectly.

Then for maximum number of edges, best way is ( k - 1 ) component are alone, only have one person ,  and one component may have ( n - k + 1 ) person.

then maximum number of edges for that component having (n - k + 1 ) person is  C( n - k + 1 , 2 ).

Comments

i understood that point that k-1 components have single member..but i want to know that how did u deduce that this configuration gives maximum edges??

---

its simple , maths( practice will do )

Let , a1 + a2  + a3 .... aN = N  

C(a1 , 2 ) + C(a2 , 2 )  + ......  C(aN , 2 )    is always  <        N * (N - 1 )/2   

where C(ai , 2 )  =  ai * (ai - 1 ) /2

---

thanks a lot :-)