En combinatoria, ¿cómo se puede verificar que se ha contado correctamente?

Question

Esta es una pregunta suave, pero he intentado ser específico sobre mis preocupaciones. Cuando estudiaba combinatoria básica, me llamó la atención el hecho de que parece difícil verificar si uno ha contado correctamente.

Es más fácil explicarlo con un ejemplo, así que daré uno (¡es divertido!) y luego plantearé mis preguntas al final. En este ejemplo hay dos formas de contar el número de formas $2n$ las personas pueden colocarse en $n$ asociaciones (del libro Introducción a la probabilidad de Blitzstein y Hwang):

$$\frac{(2n)!}{2^n \cdot n!} = (2n - 1)(2n - 3) \cdots 3 \cdot 1$$

Prueba de historia para el lado derecho: Para la primera persona tienes $(2n - 1)$ opciones de pareja. Entonces para la siguiente persona tienes $(2n - 3)$ opciones, etc.

Prueba de historia para el lado izquierdo: Línea todo $2n$ la gente se levanta, recorre la fila y selecciona cada 2 personas como pareja. El orden que elijas para la fila determina las parejas, y hay $2n!$ formas de pedir $2n$ personas. Pero dividir por $2^n$ porque el orden dentro de cada emparejamiento no importa. Divida también por $n!$ porque el orden de los emparejamientos no importa.

Mi pregunta es:

¿Y si me hubieran encargado obtener esta cifra en el trabajo y hubiera elegido el método de la izquierda, pero me hubiera olvidado de dividir por $2^n$ y sólo dividido por $n!$ ? Me equivocaría, por supuesto, pero ¿cómo iba a saberlo?

Supongo que una respuesta a mi pregunta podría ser simplemente "Esfuérzate, trata de pensar en las formas en que podrías estar contando de más/de menos, mira otros ejemplos y sigue estudiando la teoría".

Pero la perspectiva de no saber si me equivoco me pone nervioso. Así que busco cosas más concretas que pueda hacer. Así que tres preguntas de rigor creciente:

• ¿Cuáles son los "hábitos mentales" específicos de los combinadores para evitar errores?
• ¿Cuáles son las técnicas específicas de validación que utilizan estas personas para comprobar su trabajo? (De mi ejemplo me viene a la mente una: Calcular lo mismo de dos maneras y confirmar la igualdad)
• ¿Existe alguna lista formal de preguntas que, si se responden, verifiquen que el planteamiento propio es correcto?

Answer 1

He aquí algunos métodos que he utilizado. Algunos ya se han sugerido en los comentarios, y ninguno de ellos es infalible.

1. Resuelve algunos casos pequeños a mano, es decir, genera todas las posibilidades, y comprueba que tu fórmula funciona en esos casos. (A menudo, resolver los casos pequeños también te sugerirá un método de solución).
2. Resuelve el problema por dos métodos diferentes. Por ejemplo, a menudo un problema que se resuelve mediante el principio de inclusión/exclusión también puede resolverse mediante funciones generatrices. O puede ser que usted puede derivar una recurrencia que la solución debe satisfacer, y verificar que su solución satisface la recurrencia; si es demasiado difícil de hacer el caso general, verificar la recurrencia se satisface para unos pocos casos pequeños.
3. Escribe un programa informático que resuelva un caso concreto del problema por "fuerza bruta", es decir, que enumere todas las posibilidades, y comprueba el recuento con tu respuesta analítica. Si todavía no sabes programar, ésta es una de las muchas razones por las que es bueno aprender a hacerlo. Por ejemplo, ¿de cuántas formas se puede hacer el cambio de un dólar? Probablemente sea más fácil escribir un programa que genere todas las formas que resolver este problema analíticamente.
4. A veces, un problema combinatorio puede reinterpretarse como un problema de probabilidad. Por ejemplo, el problema de contar todas las manos de póquer que forman un full está estrechamente relacionado con la probabilidad de sacar un full. En este caso, puede comprobar su respuesta mediante una simulación de Montecarlo: utilice un generador de números aleatorios para simular muchas manos con el ordenador y cuente el número de manos que forman un full. Una vez más, esto requiere conocimientos de programación informática. No obtendrá una coincidencia exacta con su análisis.

Answer 2

Aquí tienes otros métodos:

• Estima cuál debería ser la respuesta. Por ejemplo, supongamos que quiero contar todos los subconjuntos de 3 elementos de $1,\dots,n$ donde la suma de dos elementos cualesquiera no es igual al tercero. Pienso para mis adentros "hmm, si $n$ es grande, entonces la mayoría de los subconjuntos de tres elementos deberían ser válidos". Así que cualquiera que sea la respuesta, sé que debe estar cerca de $\binom{n}{3}$ si $n \gg 0$ .

• Ten en cuenta también que tu intuición sobre el tamaño de la respuesta puede ser errónea. No pasa nada. Significa que reflexionarás más sobre el problema.

• Haz que alguien revise tu trabajo. Esto puede funcionar muy bien porque, a veces, cuando estás escribiendo, en el fondo de tu mente hay algo en lo que te estás equivocando. Cuando esto ocurra, lo que escribas (con suerte) les parecerá gracioso a los demás, mientras que a ti te costará mucho darte cuenta de que algo no está bien.

• Sea más riguroso. Obviamente, es más fácil decirlo que hacerlo. Por ejemplo, si estás aplicando un teorema, asegúrate de que cumples todas las hipótesis necesarias para poder aplicarlo.

• Ve más despacio y piensa "¿por qué estoy multiplicando aquí?" o dividiendo, o diferenciando. Asegúrate de que el álgebra tiene sentido combinatorio. Si estás dividiendo, asegúrate de que acabas con números enteros donde debería haber números enteros.

Answer 3

Es posible ser riguroso en cuestiones como ésta, aunque puede llevar mucho trabajo.

El primer paso es construir un modelo matemático que responda a la pregunta. Esta parte merece cierta reflexión, y hay margen para el error, pero normalmente sólo expresar la pregunta matemáticamente es más fácil hacerlo sin errores que encontrar la respuesta real .

Para este ejemplo, podríamos decir que a asociación de un grupo de $2n$ personas (a las que nos referiremos como $G=\left\{0, 1, \ldots, 2n-1\right\}$ ) es cualquier función $p: G \rightarrow G$ tal que:

• Para todos $m$ : $p(p(m)) = m$ (es decir, se empareja a la pareja de una persona)
• Para todos $m$ : $p(m) \neq m$ (es decir, nadie se asocia consigo mismo)

Espero que quede bastante claro que lo anterior se corresponde con la definición de asociación de la pregunta; si no es así, puedes hacerlo de una forma que te resulte más clara.

Una vez hecha esta definición, la pregunta es: ¿cuántas de estas funciones $p$ ¿están ahí?

Una forma de establecer la respuesta de forma rigurosa es llegar a una biyección $B$ entre el conjunto de asociaciones $P = \{p: p \,\hbox{is a partnering of $ 2n $ people}\}$ y un subconjunto inicial de los números naturales $\mathbb N$ .

Esto puede hacerse de la siguiente manera: omitiré muchos detalles por brevedad, pero espero que quede claro que puede hacerse con todo rigor. Dada una asociación $p$ :

Comience con un juego $U_0=G$ de personas sin pareja, y un valor $v_0=0$ . En cada paso $k$ a partir de 0:

• Piense en la persona de $U_k$ con el número más pequeño - llámelos $g_k$ .
• Averigüe con quién están asociados, es decir, evalúe $p(g_k)$ - y encontrar el "rango" de esa persona en $U_k\setminus g_k$ a partir de 0. Es decir, si (de todas las personas que no sean $g_k$ que hasta ahora no tienen pareja) $p(g_k)$ tiene el número más bajo, llámelos rango 0, y si hay tres con números inferiores a $p(g_k)$ que no tienen pareja, llámalos de rango 3, y así sucesivamente. Llama a ese rango $r_k$ .
• Establecer $U_{k+1} = U_k \setminus \{g_k, p(g_k)\}$ y $v_{k+1} = v_k\left|U_k-1\right| + r_k$ . Es decir, quitamos a las dos personas con las que acabamos de asociarnos, y calculamos un nuevo valor a partir del valor del paso anterior y el rango de la persona con la que acabamos de asociarnos $g_k$ .

Repita para $k$ de 0 a $n-2$ y toma $v_{n-1}$ como nuestro resultado para $B(p)$ .

Está claro que, dada cualquier asociación $p$ este procedimiento nos devuelve un número $B(p)$ . Lo que puede no estar claro todavía es que, dado $B(p)$ podemos determinar qué $p$ era - es decir, $B$ es una biyección.

No entraré en detalles al respecto, pero ten en cuenta que, al calcular el valor, la persona que queda emparejada con la persona 0 tiene su rango multiplicado por $(2n-3)(2n-5)\ldots1$ y podemos recuperarlo dividiendo $B(p)$ por ese número - la parte entera de la respuesta nos da $p(0)$ y luego podemos utilizar el resto de manera similar para deducir el resto de los emparejamientos en $p$ .

Así que (de nuevo estoy omitiendo algunos detalles de la prueba) tenemos una función que es una biyección entre $\left\{0,1,2,\ldots,m-1\right\}$ y el conjunto de posibles emparejamientos de $2n$ personas. Esto basta para demostrar que hay $m$ y es razonablemente fácil ver (tomando el máximo valor posible en cada paso del procedimiento anterior) que el valor de $m$ es exactamente $(2n-1)(2n-3)\cdots 1$ como ya sabías.