Say we need to find an expression for the number of binary strings of length $n$, which have at most $k$ ones. My solution was to split the problem into $k+1$ cases, where the number of ones, $m=0,1,2,...,k$, and sum the values together.

For example, to find the number of solutions in which at most $3$ ones occur in a $6$ bit string, we compute $\binom{6}{0}+\binom{6}{1}+\binom{6}{2}+\binom{6}{3}=1+6+15+20=42$. More generally,

$$ N=\sum_{m=0}^{k}\binom{n}{m} $$

This is pretty nice, but I'd like to find a nicer expression which doesn't involve a summation, if such a thing exists. Any suggestions?

  • 2
    $\begingroup$ There is no such summation, I remebered reading it in a book called A course in enumeration by Marting Aigner. It says it doesn't exist and it says why, but I'm too much of a noob to understand it. It's in chapter $4 which is called hypergeometric series. $\endgroup$ – Jorge Fernández Hidalgo Jan 6 '15 at 22:15

Your Answer

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

Browse other questions tagged or ask your own question.