Contar el número de cadenas de n bits con un número par de ceros.

Question

Actualmente estoy auto-estudio introductorio de la combinatoria mediante la lectura de Introducción a la combinatoria de las matemáticas. Actualmente estoy en el primer capítulo, y tengo una pregunta sobre uno de los ejemplos. La pregunta estaba pidiendo a contar el número de n bits cadenas con un número par de ceros. La respuesta es, por supuesto,$2^{n-1}$. El autor dio 2 soluciones. Sin embargo yo no entendiera lo que yo creo que es sencilla. La solución que me dieron fue que sacó de 1 bit, dejando $(n-1)$ bits, si el número de ceros es incluso en el $(n-1)$-el número de bits, a continuación, se le acaba de añadir un 1, si no, entonces él se añadirá un cero. Así que al final sólo necesitábamos para contar el número de $(n-1)$-cadenas de bits. La otra solución (el sencillo) que yo no entendía examinó la simetría que la mitad de la $2^n$ debe tener un número par de ceros, y la otra mitad tendrá un número impar de ceros. Yo no entiendo por qué esta propiedad debe mantener. Puedo entender que la mitad de la $2^n$ números tendrán incluso la paridad, pero no puedo ver cómo se sostiene por la paridad en el número de cero o más bits. Si alguien me puede mostrar cómo que posee propiedad, estaría muy agradecido. También me gustaría estar interesado en ver las diferentes explicaciones y pruebas, si es posible.

Gracias.

Answer 1

Dividir el $2^n$ cadenas en dos grupos, uno con un número impar de ceros y uno con un número par de ceros. Si usted toma cualquier cosa, desde el "raro" del grupo, y de vuelta a la primera bits, se obtiene algo en el "grupo". Del mismo modo, orientando el primer bit de la nada en el "incluso" grupo va a producir algo en el "raro" del grupo.

Una vez que te das cuenta de que no hay ninguna posibilidad de superposición (que es, de arrojar dos diferentes cadenas no pueden dar el mismo resultado), significa que los dos grupos han de ser exactamente el mismo tamaño.

Answer 2

Un enfoque estándar es que el número de cadenas con un número par de %#% de $0$ #% $ el número con un número impar de %#% de $$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots.$ #% $

Recordemos que por el teorema del binomio, $0$$ Put $$\binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\cdots.$. Tenemos $$(1+x)^n=\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\binom{n}{3}x^3+\binom{n}{4}x^4+\cdots.$ $ así que el número con un número par de $x=-1$ es el mismo que el número con un número impar de $$0=\binom{n}{0}-\binom{n}{1}+\binom{n}{2}-\binom{n}{3}+\binom{n}{4}-\cdots.$'s.

OverKill, pero este enfoque puede ser utilizado para otros resultados de funciones generatrices. No primer capítulo de la materia, tal vez segundo.