# No. of ways of selecting more than 50% of the elements

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 }

-
@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

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

-
it wasn't multiplied. Clear now? –  Adwait Kumar Feb 2 '13 at 15:22