Closed formula to count number of binary numbers of length $x$ having at least $y$ $1$ bits

Question

I'm interested in solving a sub problem of the algorithm related question from SO How many binary numbers having given constraints .... The sub problem being, having $x \geq y$

• determine how many binary numbers of length $x$ have at least $y$ $1$ bits

The immediate algorithm is to go over all $2^x$ binary numbers and count the ones having at least $y$ $1$ bits. Time complexity of such algorithm is $O(2^x)$ or even $O(x2^x)$ since for each number, one has to count the $1$ inside using a loop through all bits (actually $x/2$ on average, but this is not the point).

My target is ideally to find a $O(1)$ algorithm, i.e. a closed formula $f$ such that $\textrm{numbers} = f(x,y)$.

I started with some observations. For $x = 5$, with x being either $0$ or $1$:

y = 1         y = 2    y = 3
1xxxx (2^4)   11xxx    111xx
01xxx (2^3)   101xx    (...)
001xx (2^2)   011xx    Σ = 1x2^2+3x2^1+6x2^0
0001x (2^1)   1001x
00001 (2^0)   0101x
              0011x
Σ = 2^5 - 1   10001
              01001
              00101
              00011

    Σ = 1x2^3+2x2^2+3x2^1+4x2^0

The number of terms is $C_x^y$ and from there it is possible to improve the initial algorithm into parsing only $C_x^y$ elements instead of $2^x$, and as a developer that could make me happy, but, and this is the question,

• is there a closed formula that gives directly the number of binary numbers of length $x$ having at least $y$ $1$ bits?

Answer 1

The required value should be the following:$$\sum_{i=0}^{x-y}\binom{x}{y+i}$$

This is because you need to select $y, (y+1), ..., x$ positions from the total $x$ positions to place $1$'s, and the rest zeroes.

This expression is just a sum of the last $y$ binomial coefficients. As far as I know, there is no general expression for the sum of $k$ binomial coefficients to give you an $O(1)$ answer.

You may find this link helpful for finding a efficient algorithm or a good bound on the sum.

Answer 2

You can build your closed formula by adding "number of terms with exactly x '1' bits" and "number of terms with exactly x-1 '1' bits" and so on.

The number of terms with length x and exactly k '1' bits (and hence x-k '0' bits) is $$ \binom {x} {k}=\frac{x!}{(x-k)!k!} $$ Now you just have to add the terms up you are interested in.