Queridos estudiantes! Cómo les va?
En esta semana hemos visto que contar no es tan simple como parecía...
Vimos que contar la cantidad de particiones de un conjunto de n elementos (o relaciones de equivalencia de tamaño n) no es trivial.
También aprendimos que Jin Akiyama (investigador empleado por Frank Harary y ahora difusor de matemática en Japón) ha logrado contar la cantidad de grafos autocomplementarios de tamaño n.
Por otra parte, el conteo de casamiento en grafos bipartitos dio nacimiento a una nueva jerarquía de complejidad de problemas de conteo, y cae dentro de la clase de problemas "intratables" en un sentido formal (de hecho, pertenece al conjunto de problemas #P-Completos, definido por L.G. Valliant en 1979).
Les invito a que profundicen de estos problemas de conteo. También, como elemento motivacional, busquen quién es Jin Akiyama, y qué libros publicó Frank Harary sobre teoría de grafos (el primer capítulo de su libro Graph Theory es una verdadera joya; no tiene desperdicio).
También vale la pena revisar el gran artículo de L. G. Valliant: "The Complexity of Computing the Permanent".
Disponemos del uso de biyecciones para transformar un problema de conteo en otro "equivalente".
Mediante la regla del producto hemos contado funciones inyectivas de n en m (o arreglos de m en n), biyectivas (o permutaciones de n objetos). A partir de un argumento combinatorio hemos contado las combinaciones de m en n.
Hasta ahora disponemos de las reglas de suma y producto, transformación de problemas mediante biyecciones, reconocimiento de
patrones (permutaciones, arreglos, combinaciones), argumentos combinatorios y, como siempre, de nuestra intuición, que
tanto ayuda a hallar atajos a la hora de contar.
La semana que viene seguiremos con otras herramientas de conteo.
Que tengan muy buen fin de semana!
Les desea,
Pablo.