# 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. Commented May 30, 2013 at 9:34
• I'm sorry. It has been corrected by someone else. Commented May 30, 2013 at 9:43
• @f.nasim, unluckily there is no closed formula for such sums. Commented Mar 4, 2014 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? Commented May 30, 2013 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. Commented Jun 1, 2013 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. Commented May 30, 2013 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. Commented May 30, 2013 at 10:47