From my years browsing math.SE, I've come to learn there's always some useful--albeit obscure--identity for every conceivable sum of combinatoric functions.

Mine is as simple as they come: $$S(n,m)=\sum _{k=0} ^m {n \choose k}$$ for $m \leq n$.

That is, a partial sum of binomial coefficients. Practically: the number of ways one can choose a subset of $m$ or fewer objects out of a set of $n$ objects.

Apologies if this is already answered elsewhere, but a search for "sum of binomial coefficients" turns up hundreds of permutations (no pun intended) of the question, none of which seem to be relevant to this specific case.

  • 2
    $\begingroup$ I doubt there are nice closed-form expressions for those, as they are essentially unnormalized tails of a binomial distribution. However, there are some very tight bounds: look up Chernoff bounds for unbiased coin flips. $\endgroup$ – amakelov Apr 7 '17 at 19:09
  • $\begingroup$ @amakelov: will do; thanks. $\endgroup$ – COTO Apr 7 '17 at 19:12

$${n\choose n-m}{\mbox{$_2$F$_1$}(1,-m;\,1+n-m;\,-1)}$$

where $\mbox{$_2$F$_1$}$ is a hypergeometric function.

See also OEIS sequence A008949.

  • $\begingroup$ I can't believe when users with 20.6K reputation are also not clear with answers. BTW, I have seen this problem before also. But never know the solution. $\endgroup$ – maverick Apr 7 '17 at 19:51
  • 1
    $\begingroup$ I linked to the Wikipedia page where there is an explanation. If you think more explanation is needed, please feel free to add your own answer. $\endgroup$ – Robert Israel Apr 7 '17 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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