So I know you could do this the tedious way of:

$(nCk) + (nCk_{+1}) + ... + (nCk_{=n})$

or the somewhat less tedious, but still not ideal:

$2^n - [(nC0) + (nC1) + ... + (nCk_{-1})]$

However, this problem to me is just screaming to think of it in terms of an $n$-bit integer, where a $1$ represents an element being present, a $0$ not present. so I guess what im asking is:

How would you determine the number of $n$-bit integers that contain at least $k$ $1$s?

Forgive me if my formatting is off, this is my first post. Tips appreciated!


This problem is actually notoriously tough, and I do not believe it has a closed form solution. Note that, by symmetry, this is equivalent to summing over the first $k$ binomial coefficients, and then see here: https://mathoverflow.net/questions/17202/sum-of-the-first-k-binomial-coefficients-for-fixed-n

| cite | improve this answer | |
  • $\begingroup$ Haha. Well now I feel silly. New to discrete maths, but have found even these elementary counting techniques quite interesting. Thanks for the response! $\endgroup$ – avcJav Dec 20 '15 at 6:07

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.