Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
up vote 3 down vote accepted

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



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|cite|improve this answer
it wasn't multiplied. Clear now? – Adwait Kumar Feb 2 '13 at 15:22

Your Answer


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.