Actualmente estoy estudiando combinatoria introductoria por cuenta propia leyendo Introducción a las matemáticas combinatorias. Actualmente estoy en el primer capítulo y tengo una pregunta con respecto a uno de los ejemplos. La pregunta era contar el número de cadenas de n bits con un número par de ceros. La respuesta es por supuesto . El autor dio 2 soluciones. Sin embargo, no entendí completamente cuál creo que es la más sencilla. La solución que obtuve fue que sacó 1 bit, dejando bits, si el número de ceros es par en el -número de bit, luego solo agregará un 1, si no, agregará un cero. Así que al final solo necesitábamos contar el número de -cadenas de bits. La otra solución (la sencilla) que no entendí examinaba la simetría que la mitad de la debe tener un número par de ceros, y la otra mitad tendrá un número impar de ceros. Simplemente no entiendo por qué esta propiedad debe mantenerse. Puedo entender que la mitad de los los números tendrán paridad par, pero no puedo ver cómo se mantiene para la paridad del número de bits cero o uno. Si alguien puede mostrarme cómo se mantiene esa propiedad, estaría muy agradecido. También me interesaría ver diferentes explicaciones y pruebas si es posible.
Gracias.
dividir el cadenas en dos grupos, uno con un número impar de ceros y otro con un número par de ceros. Si toma algo del grupo "impar" y voltea el primer bit, obtendrá algo en el grupo "par". De manera similar, voltear el primer bit de cualquier cosa en el grupo "par" producirá algo en el grupo "impar".
Una vez que te das cuenta de que no hay posibilidad de superposición (es decir, cambiar dos cadenas diferentes no puede dar el mismo resultado), significa que los dos grupos deben tener exactamente el mismo tamaño.
Un enfoque estándar es que el número de cadenas con un número par de es
Recuerde que por el teorema del binomio,
Overkill, pero este enfoque de funciones generadoras se puede utilizar para otros resultados. No cosas del primer capítulo, tal vez del segundo.
turingcompleto