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

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?
• I think closed formula for $x \choose y$ + $x \choose y + 1$ + ... + $x \choose x - 1$ + $1$ is the desired answer. – f.nasim May 30 '13 at 9:34
• I'm sorry. It has been corrected by someone else. – f.nasim May 30 '13 at 9:43
• @f.nasim, unluckily there is no closed formula for such sums. – vonbrand Mar 4 '14 at 15:10

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.

• Ok, it seems I cannot get rid of the loop. Let see if someone else comes with a better answer... or, if not, I'll accept this one. Btw, the $C_x^y$ notation is not of usage anymore? – Ring Ø May 30 '13 at 10:53
• Based on the link I am sure there is no closed form expression for the sum. I do not think so; the $\binom{y}{x}$ notation is clearer and easier to read than $C^y_x$. especially when one of the arguments is a longer expression. – Milind Jun 1 '13 at 3:56

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.

• Btw, you asked for a O(1) algorithm. Calculating n! is quite expensive, it is in the range of O(n). To come to O(1) you have to use an aproximation. See here for details. – stefan.schwetschke May 30 '13 at 10:33
• Thanks, I'm looking for exact values, with the lowest complexity. Please see Milind Hegde's answer who provides a valid answer. – Ring Ø May 30 '13 at 10:47