Is there a way to (efficiently) compute the number of numbers up to $n$ with $k$ set bits?
Some values for low $n$ and $k$ as an example (perhaps $n$ is off by one); "#" is the number of set bits in the binary representation of $n$ ("Hamming weight", popcnt).
n # k=0 k=1 k=2 k=3 k=4
------------------------------------
0000 0 1 0 0 0 0
0001 1 1 1 0 0 0
0010 1 1 2 0 0 0
0011 2 1 2 1 0 0
0100 1 1 3 1 0 0
0101 2 1 3 2 0 0
0110 2 1 3 3 0 0
0111 3 1 3 3 1 0
1000 1 1 4 3 1 0
1001 2 1 4 4 1 0
1010 2 1 4 5 1 0
1011 3 1 4 5 2 0
1100 2 1 4 6 2 0
1101 3 1 4 6 3 0
1110 3 1 4 6 4 0
1111 4 1 4 6 4 1
While trying to figure out a solution I eventually realised, that this is relatively straight forward when $n$ is a power of 2 (because all combinations of bits are guaranteed to appear). In that case the value I am after is $f_k(n)=C{log_2(n)\choose k}$. But as far as I can see this does not help for arbitrary $n$.