Cómo muchos de 19 de cadenas de bits que pueden ser generadas de tener un número par de unos?

Question

Así que, esencialmente, cómo muchos de 19 de cadenas de bits se puede hacer con 2 a 1 o 4 a 1 o .... o 18 1?

Sé el # de 19 de cadenas de bits que puede ser producido con el 2 a 1 que sería el 19!/17!2! y el número de 19 de cadenas de bits que puede ser producido con el 4 a 1 que sería 19!/15!4! ..... hasta el 19!/18! en el caso donde hay 18 1. Lo que no entiendo es ¿cuánto se solapan.

Sé que este problema tiene que ver con la inclusión-exclusión principio, estoy confundido sobre cómo calcular la intersección de cada resultado posible.

Answer 1

hacer cualquier cadena de caracteres con el puño de 18 dígitos. El último dígito es forzado a ser un 1 o un 0, basado en el número de 1s en los primeros 18.

Answer 2

Que no se superponen en lo que cuentan; si una cadena tiene cuatro $1$s, entonces no puede tener también seis $1$s. Así que usted sólo tiene que tomar una suma sobre estas posibilidades.

Una manera más sencilla utiliza el siguiente truco: si una cadena de longitud $19$ tiene un número impar de 1s, entonces su complemento (sustituye todos los $0$s $1$s y $1$s $0$s) tiene un número par de unos, y viceversa. Así que toma todas las posibles cadenas binarias y solo hay que dividir por $2$.

Answer 3

Me gusta la aceptación de la solución, pero yo sólo quería decir algo sobre la forma de hacer las matemáticas de los "duros". Usted sabe que hay $\binom m k = \frac{m!}{k!(m-k)!}$ maneras de elegir un conjunto de $k$ elementos de un conjunto de $m$ artículos. Esos elementos pueden ser numerados bits elegido para ser 1s o 0s. Por supuesto, usted sabe la identidad que: $$\sum_{k=0}^m \binom m k = 2^m$$ because of course if you sum up all the ways you might choose $k$ bits to be 1, then you get all possible bitstrings. However there is a simple proof of this which hinges on the idea that these coefficients appear in the binomial expansion, $$\sum_{k=0}^m \binom m k ~x^k ~y^{m-k}= (x + y)^m.$$ Just plug in $x = y = 1$ para encontrar la fórmula anterior como un caso especial.

Bueno, ahora que usted quiera considerar sólo bitstrings, y así todavía podemos "hacerlo de la manera difícil" pidiendo una función de $k$ $1$ si $k$ es par o $0$ si $k$ es impar, y un gran ejemplo es $[1 + (-1)^k]/2.$ Conectar ese en, la cantidad de dinero que quieres es simplemente $$\sum_{k=0}^m \binom mk \frac{1 + (-1)^k}2 = \frac12 \sum_{k=0}^m \binom mk + \frac12 \sum_{k=0}^m \binom mk (-1)^k.$$ The first sum is clearly $2^m/2 = 2^{m-1}$ and the second sum we can use the above formula to reason that it is actually $(-1 + 1)^m/2 = 0^m/2 = 0.$

Así que usted puede hacer esto de la manera difícil, si usted prefiere, y definitivamente va a obtener el mismo resultado.

Answer 4

Desde el enfoque que tomó para el problema, mi primera idea fue usar el hecho de que $\binom{19}{k}=\binom{19}{19-k}$; debido a $19$ es impar se sigue que $$\sum_{\substack{k=0\\k\text{ par}}}^{19}\binom{19}{k} =\sum_{\substack{k=0\\k\text{ par}}}^{19}\binom{19}{19-k} =\sum_{\substack{k=0\\k\text{ impar}}}^{19}\binom{19}{k}.$$ La adición de la mano izquierda y la mano derecha juntos podemos obtener la suma de todos los $k$, por lo que $$2\times\sum_{\substack{k=0\\k\text{ even}}}^{19}\binom{19}{k}=\sum_{\substack{k=0\\k\text{ even}}}^{19}\binom{19}{k}+\sum_{\substack{k=0\\k\text{ odd}}}^{19}\binom{19}{k}=\sum_{k=0}^{19}\binom{19}{k},$$ y esto es igual a $2^{19}$ por el teorema del binomio, véase también el CR Drost la respuesta. Entonces, la respuesta es $2^{18}$.

Pero me gusta Doug M respuesta mucho mejor.

Answer 5

Deje $c=(x_1,\cdots,x_{19})$$\bar c=(1-x_1,\cdots,1-x_{19})$. Tenemos un mapa $$c \to \bar c \to \bar{\bar c}=c.$$ Since $19$ is odd, for any odd(even)$c$ we will get an even(odd) $\bar c$. Therefore, the number is $$2^{19}/2=2^{18}.$$

Tenga en cuenta que: $c_1\ne c_2$ implica (trivialmente) $\bar c_1\ne \bar c_2.$