Cómo comprobar mi respuesta en problemas de combinatoria

Question

Los problemas de combinatoria (combinaciones y permutaciones) son una asignatura absolutamente desquiciante para mí. Parece que puedo llegar a la respuesta, siempre que ya conozca la respuesta correcta. Sin embargo, rara vez consigo dar con la respuesta correcta a la primera. Obviamente, esto es un problema en los exámenes.

En álgebra y cálculo, normalmente puedo comprobar que una respuesta es correcta trabajando hacia atrás o introduciendo el resultado en la ecuación original.

¿Hay alguna forma de hacer lo mismo con los problemas de enumeración?

Answer 1

Intento escribir una frase explicando qué cuento exactamente a ambos lados de la igualdad, para convencerme de que son lo mismo. Por ejemplo, para la identidad

${n \choose k} + {n \choose k+1} = {n+1 \choose k+1}$

Yo escribiría el lado izquierdo primero cuenta todos los subconjuntos de $[n+1]$ de tamaño $k+1$ que incluyen el elemento $n+1$ más el número de subconjuntos de $n+1$ que no incluyen $n+1$ . Por otro lado, el lado derecho cuenta el número de subconjuntos de $[n+1]$ de tamaño $k+1$ .

Aunque la identidad original no parece necesariamente obvia, cuando se escribe en un texto parece casi trivial. Esto requiere mucha práctica, pero cuando se hace "clic" y se pueden escribir fácilmente descripciones como ésta, es muy fácil comprobar las respuestas en combinatoria.

Answer 2

Una de las cosas más importantes es que entiendas exactamente qué estructuras quieres contar (asegurándote de cuándo dos de ellas son iguales, por ejemplo). Una vez que sepas esto, puedes probar si tu fórmula funciona en casos pequeños que puedes resolver a mano.

Answer 3

Mi mejor sugerencia para los problemas de enumeración es plantearlos como una secuencia de pasos definidos explícitamente que se multiplican por el principio de multiplicación (o que suman un conjunto disjunto por el principio de suma). A continuación, compruebe los pasos simulando su respuesta. A continuación, comprueba también si existe otra secuencia de opciones que llegue a la misma respuesta. Si es así, es posible que tenga que dividir para tener en cuenta el exceso de recuento (suponiendo que el mismo problema se produce para cualquier secuencia de opciones).

Por ejemplo: ¿Cuántos diferente Las manos de dos parejas existen en una mano de 5 cartas de una baraja estándar de 52 cartas. (En este caso, una pareja doble consiste en tres números distintos, dos de los cuales se repiten, por ejemplo: $J\heartsuit J\spadesuit 5\heartsuit 3\clubsuit 3\diamondsuit$ )

Podrías responder de la siguiente manera: (ten en cuenta que esto es ligeramente incorrecto, como se muestra más adelante)

Paso 1: Elige el número de la primera pareja: $\binom{13}{1}$

Paso 2: Elige los trajes para la primera pareja: $\binom{4}{2}$

Paso 3: Elige el número del segundo par: $\binom{12}{1}$

Paso 4: Elige los trajes para el segundo par: $\binom{4}{2}$

Paso 5: Elige el número para el singleton: $\binom{11}{1}$

Paso 6: Elige el palo para el singleton: $\binom{4}{1}$

Una secuencia específica de elecciones debe conducir a un resultado único, lo que significa que si se cambia al menos una elección, debe conducir a un resultado diferente.

Considera las respuestas a los pasos: $(J)(\heartsuit \spadesuit)(3)(\clubsuit \diamondsuit)(5)(\heartsuit)$ . Compárelo con $(3)(\clubsuit \diamondsuit)(J)(\heartsuit \spadesuit)(5)(\heartsuit)$ . Dado que la respuesta a la primera pregunta es diferente, habríamos contado cada una de estas secuencias de respuestas por separado; sin embargo, observe que ambas describen exactamente la misma mano de póquer (ya que el orden de las cartas en la mano no importa). En general para este problema, cualquier elección que hagas en los pasos 1 y 2 puede intercambiarse con las elecciones hechas en los pasos 3 y 4 para llegar exactamente a la misma mano. Por lo tanto, contamos cada mano (al menos) dos veces. Puede convencerse de que ha contado cada mano sólo dos veces. Como tal, puede dividir por 2 debido a la simetría para llegar a la respuesta correcta.

Esto se extiende a otros tipos de problemas de combinaciones y permutaciones más allá de los problemas de manos de póquer. Pregúntese si barajando las respuestas se llega a resultados "iguales" o "diferentes", y pregúntese si hay más de una forma de llegar al mismo resultado a partir de una secuencia de elecciones, o si hay algún resultado al que no se pueda llegar mediante ninguna secuencia de elecciones.

Answer 4

Aunque agradezco las respuestas dadas por otros, mi pregunta era si hay alguna forma de comprobar directamente la validez de una respuesta a problemas de enumeración.

Lo que otros han sugerido de forma útil son más o menos heurísticos para llegar a la respuesta correcta.

Después de pensarlo durante algún tiempo, he llegado a la conclusión de que la simulación es la única respuesta adecuada para comprobar directamente la corrección. Aunque esto es imposible para algunos problemas debido a la enorme cantidad de cálculos necesarios para comprobar todas las posibilidades, reducir el tamaño del problema debería permitir comprobar un subconjunto razonable del mismo.