Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Out of N different elements what is the total number of possible selections such that the number of objects selected is always greater than the number of objects left behind? eg: for N=4 elements it is 5. {By :4C3+ 4C4 }

share|improve this question
    
@Maesumi 5 is the no. of ways of selecting out of 4 objects as per the constraints of the question –  Adwait Kumar Feb 2 '13 at 15:13
add comment

1 Answer 1

If you are to choose a team from at least half of players A,B,C,D, then your choices are

ABCD

ABC, ABD, ACD, BCD

that is 4C4+4C3=5 as you noted.

You just need to add the binomial coefficients.

(a) If $n$ is odd then they add up nicely to $2^{n-1}$.

(b) If $n$ is even then you have a middle term too and you get $2^{n-1}-{1 \over 2} {\left( n \atop {n/2}\right)}$.

Note $(a+b)^n=\sum_{k=0}^n {\left( n \atop {k}\right)} a^k b^{n-k}$. Sum of all binomial coefficients is obtained by setting $a=b=1$ then $2^n=\sum_{k=0}^n {\left( n \atop {k}\right)}$.

To see (a) you need to add half of all binomial coefficients and due to their symmetry, $ {\left( n \atop {k}\right)}={\left( n \atop {n-k}\right)}$, you just get a total of $2^{n-1}$.

To see (b) you need to add half of all terms except the middle one so use ${1 \over 2}\left[\sum_{k=0}^n {\left( n \atop {k}\right)} -{\left( n \atop {n/2}\right)}\right]= 2^{n-1}-{1 \over 2} {\left( n \atop {n/2}\right)} $

share|improve this answer
    
it wasn't multiplied. Clear now? –  Adwait Kumar Feb 2 '13 at 15:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.