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?
24 votos
Comprobar si la respuesta es pequeña $n$ (en los casos en los que se puede contar manualmente) es una buena comprobación de cordura.
70 votos
En 1962, en mi segundo año de Introducción a la Probabilidad, mi profesor preguntó cuántas patas tenía una vaca. Explicó que tenía doce: dos delante, dos detrás, dos a la izquierda, dos a la derecha y una en cada esquina. No nos hizo ninguna gracia. Unas semanas más tarde contó el mismo chiste y todo el mundo se rió.
0 votos
¿Qué quiere decir con "comprobar si hay pequeñas $n$ "? ¿Quieres decir que si tengo pequeñas $n$ ¿Puedo escribir exhaustivamente todas las posibilidades?
0 votos
@Stephen En tu ejemplo, tienes una fórmula que funciona para todos los $n$ . Si quieres comprobar que no has contado de más o de menos, puedes calcular los casos $n=2$ o $n=3$ manualmente para asegurarnos. Esto no es infalible, sino más bien para comprobar si hay algunos errores.
0 votos
Ok gracias, eso es lo que pensé que querías decir. Y sí, estoy de acuerdo, que parece una buena / fácil cordura comprobar.
9 votos
A menudo, no se puede estar seguro. Y esa es una de las razones por las que personalmente no me gusta la combinatoria: nunca estoy seguro de si he metido la pata hasta el fondo. :)
3 votos
Creo que fue en el prefacio de la 3ª edición de "Generatingfunctionology" donde leí que la mayoría(?) de las pruebas biyectivas (léase de recuento) que conocemos se descubrieron por primera vez tras trastear con funciones generadoras en primer lugar. Y aparentemente "A = B" de Petkovsek (y otros) proporciona uno o varios métodos completamente probados para resolver la mayoría de los problemas de los libros de texto del tipo que has mencionado. Aún no he leído ninguno de los dos, pero búscalos en Google y compruébalo por ti mismo.
0 votos
O tal vez un mejor ejemplo de cómo podría haber elegido incorrectamente: Ingenuamente habría pensado (en el caso en el que se buscan 5 emparejamientos de 10 personas) que la respuesta es $\binom{10}{2} \binom{8}{2} \binom{6}{2} \binom{4}{2} \binom{2}{2}$ . Resulta que eso está muy mal, pero no estoy seguro de por qué. Es mira ¡Bien!
2 votos
@Stephen Si divides eso por $5!$ : $$ \frac{ {10 \choose 2}{8 \choose 2}{6 \choose 2}{4 \choose 2}{2 \choose 2}}{5!}$$ obtendrás la respuesta correcta.
0 votos
@T.Gunn ¡Bien, tienes razón! ¿Cómo se puede saber si es necesario dividir por ordenaciones totales así? Estaba tratando de pensar en una buena regla y se me ocurrió: "Dividir por r! cuando el orden no importa, donde r es el número de cosas que de otro modo estarían ordenadas". ¿Se puede decir algo más? Quizá el problema es que, como no impongo explícitamente un orden, no me doy cuenta de que aún necesito contrarrestar el orden que surge de forma natural.
0 votos
@Stephen Experiencia para decirlo simplemente. Una vez que te has equivocado suficientes veces te familiarizas más con cómo son las trampas. Sé, por ejemplo, que cuando tienes un producto $a_1 \cdot a_2 \cdots a_n$ que procede de un producto cartesiano $A_1 \times A_2 \times \cdots \times A_n$ . Los productos cartesianos son tuplas ordenadas.
0 votos
Ahora, no estoy pensando "producto = producto cartesiano = tuplas ordenadas = ordenadas" en mi cabeza. Estoy pensando "primero elige 2 elementos de 10, luego elige 2 elementos de 8... ¿qué es 8? ese es el número de elementos restantes. Luego elige 2 elementos de los 6 restantes". Luego vuelvo atrás y pienso "primero elegí estos dos, luego segundo elegí estos dos, luego tercero, estos dos... primero, segundo, tercero, eso es 1, 2, 3 que es un orden, ¡debería dividir por 5!".
0 votos
@Stephen Tú mismo hiciste algo de eso. Nunca te dije por qué para dividir por 5!, pero una vez que te lo dije, sabías lo que dividir por 5! hace a la fórmula. Todas las operaciones de esa fórmula: los coeficientes binomiales, multiplicar, restar 2 del número superior cada vez, ¡dividir por 5!. Todas ellas tienen un significado.
0 votos
Sólo un breve comentario: ''Principles and Techniques in Combinatorics'', de Chen Chuan-Chong y Koh Khee-Meng, es un libro muy completo: teoría, ejercicios y respuestas :) Uno de los mejores que hay. Los libros mencionados por user448692 ("generatingfunctionology", y ''A=B'') también son clásicos en su campo. R.P. Stanley ha escrito la biblia de la combinatoria en 2 volúmenes, ''Enumerative Combinatorics'', para aquellos que realmente conocen sus multinomios.
0 votos
He creado un programa, del que hice una demostración aquí, para ayudar a verificar las soluciones de recuento: youtu.be/uNSJFOX_fxM