¿Cuál es la fórmula para encontrar todos los números binarios, por debajo de B con el número de bits == 1 mantenerse en constante?

Question

Tal vez explica mejor con un ejemplo:

Número binario B = 1100, cada número es menor que B es 1010, 1001, 0110, 0101, 0011. (Con 2 bits == 1)

Así que el total de formas de expresar el número de B y de todos los números menores que B, que contiene 2 bits == 1 es de 6, o 3+2+1.

Sospecho que esta es una de las Combinaciones problema, pero mis habilidades matemáticas son una especie de rusty, y yo no puede deducir una fórmula consistente para diferentes números binarios.

He hecho mi búsqueda en la web, pero no pude encontrar nada que me dio una respuesta a este problema en particular.

Answer 1

Si $B$ no es de la forma $2^k-1$, de modo que el mayor número de con $k$ bits, es más fácil dividir el problema en dos. Encontrar $k$, el mayor número tal que $2^k-1 \lt B$. Deje $n$ el número de bits que desea. A continuación, a a $2^k-1$ hay $k \choose n$ a dichos números. En el rango de $[2^k,B]$ tienes que tener el bit inicial de un $1$, por lo que puede optar $n-1$ más bits. Es el mismo que el número de números con $n-1$ bits en el rango de $[0,B-2k]$, lo que da un algoritmo recursivo:

función numérica(B,n): devuelve el número de números de menos de o igual a $B$ $n$ bits en la base 2

$k=\lfloor \log_2 (B+1) \rfloor$: vamos a $k$ ser el número más grande tal que $2^k-1 \le B$

si $B=2^k-1$: regresar $k \choose n$
otra cosa: regresar ${k \choose n} + \text{nums}(B-2^k,n-1)$

Answer 2

Deje $F(x,y) = \sum_{n = 0}^\infty x^n y^{s_2(n)}$ donde $s_2(n)$ es el número de 1s en $n$'s representación binaria. Entonces $$ F(x,y) = F(x^2, y) + xy F(x^2,y) $$ Por lo tanto $$ F(x,y) = (1 + xy)F(x^2,y) $$ Para un determinado $n$, se desea calcular el número de $n' \le n$ que tienen el mismo número de 1s en binario como $n$. Así que vamos a $G(x,y)$ ser la generación de la función donde el coeficiente de $x^n y^k$ es el número de números enteros de menos de o igual a $n$ $k$ 1s en su representación binaria. Entonces $$ G(x,y) = (1 + x + x^2 + \cdots) F(x,y) \implica F(x,y) = (1-x)G(x,y) $$ Por lo tanto \begin{align*} (1-x)G(x,y) &= (1 + xy)(1 - x^2)G(x^2,y) \\ G(x,y) &= (1 + xy)(1 + x) G(x^2,y) \end{align*}

El problema se reduce a la extracción de los coeficientes de la función de la generación de $G(x,y)$. Uno puede escribir un algoritmo para hacer esto, pero una fórmula exacta es probable que no va a fácil.

Answer 3

Versión corta: si el número de $n$ $1$s en las posiciones de los bits $\{i_1,i_2,\dots,i_k\}$ (donde contamos de partida con la posición de bit $1$), a continuación, el número de los números binarios, que son menos de $n$ y tienen exactamente $k$ $1$s es $$ \binom{i_k-1}{k} + \binom{i_{k-1}-1}{k-1} + \dots + \binom{i_1-1}{1} . $$ En su ejemplo, usted tiene $k=2$, las posiciones de los bits $\{3,4\}$ por lo que el número de es $\binom{3}{2}+\binom{2}{1}=5$.

Versión larga: creo que de este problema como uno de la clasificación y unranking $k$-subconjuntos de a $[n]=\{1,2,\dots,n\}$ en el colex orden. Tenemos el fin de subconjuntos de a $\mathbb N$ en el colex orden diciendo $B<A$ si $\max(A \Delta B) \in A$, o en otras palabras, el elemento más grande que ellos tratan de forma diferente en $A$. La correspondencia con los números en binario es por las posiciones de $1$s. Si $A$ $k$- establecer el número de predecesores en colex fin es la unión de $k$-conjuntos de $B$ con $\max(B)<\max(A)$, $k$-conjuntos con $\max(B)=\max(A)$, pero que se diferencian en que el segundo elemento más grande, y así sucesivamente. Estos conjuntos son contados por los términos de la suma anterior.

Answer 4

Gracias a todos los que respuestas. Algunos de sus matemáticas es un bocado (para mí!).

http://en.wikipedia.org/wiki/Permutations me dio la respuesta, utilizando factoriales. La figura denominada "Permutaciones de multisets" me dio la solución. Consulte la columna de la derecha en la figura con 2 bolas rojas y 2 bolas de color azul. Cuando hacemos caso omiso de la orden de las bolas, es la solución perfecta para el problema planteado.