jueves, 5 de diciembre de 2013

Analytic Combinatorics, de Philippe Flajolet y Robert Sedgewick

He adquirido un superpoder.

La sensación que produce acabar este libro es la de «ya sé kung fu». ¿Cuántas veces os habéis topado con un problema de combinatoria y habéis resoplado ante la idea de tener que encontrar una fórmula general (o por lo menos asintótica) para el resultado? Da mucha flojera, ¿verdad? Son problemas endiabladamente intrincados en los que hay que tener especial cuidado para no contar varias veces la misma cosa, o para no olvidarte de contar nada. Los factoriales, números combinatorios, sumatorios, etc., se combinan de formas tan complicadas que te llegas a sentir abrumado, por no hablar de muy poco optimista respecto al resultado final. ¿Me creeríais si os dijera que después de leer este libro (¡ni siquiera!: basta la primera parte), problemas que no os habríais ni atrevido a plantear, os van a parecer una cuenta chorra? Es más, dan ganas de ponerse a contar estructuras cada vez más complicadas, sólo para sentir el superpoder.

Cuenta Daniel Dennett, en La peligrosa idea de Darwin, que la teoría de la evolución es como el ácido universal. Una vez que la entiendes, ya nada resiste su poder corrosivo y se traga todo el universo conocido. ¡No lo resiste ni Dios! Pues el análisis matemático posee la misma capacidad disolvente. Es un arma poderosa que engulle la matemática entera a su paso, incluso las ramas más alejadas del continuo, llevándolas a límites a priori inconcebibles. La geometría, la teoría de números, la combinatoria... Nada se le resiste. Hay matemáticos que desprecian profundamente este poder del análisis, y no les falta cierta razón: si uno es sensible a la naturaleza estética de la matemática no puede pasar por alto que, una vez que el análisis llega a alguna de sus disciplinas, todo se vuelven funciones, derivadas, integrales y demás. En la combinatoria hay auténticos talibanes que se niegan a usar niguna herramienta que no forme parte de la lógica de la disciplina. Y sin embargo, hay que reconocer que hay una gran belleza en la manera en que el análisis consigue unificar conceptos tan dispares y encontrar conexiones que permanecían ocultas. Pero sobre todo, para quienes nos interesa principalmente el aspecto práctico de la cuestión, el análisis es nuestro gran aliado.

De eso trata este libro. La manera de conectar la combinatoria y el análisis es a través de las funciones generatrices. Una función generatriz es, como dice Wilf en Generatingfunctionology (otro gran libro, sorprendentemente ameno de leer), un «tendedero» en el que colgar una sucesión, en este caso la sucesión que cuenta el número de elementos de «tamaño» n de un cierto conjunto. Lo grande del procedimiento es que transformamos la sucesión, por lo general difícil de manejar, en una función, el concepto básico del análisis matemático. Convertimos, así, el problema de hallar la sucesión que cuenta los elementos de esos conjuntos en el de hallar una solución a una ecuación (algebraica, diferencial, integral...), algo para lo que el análisis posee infinidad de herramientas. Pero la magia de este libro es cómo se llega a la función con un esfuerzo mínimo. Para ello lo que hace es construir un lenguaje formal que permite describir el problema combinatorio en términos muy sencillos, y proporcionarnos su traducción a ecuaciones. La solución de tales ecuaciones es la función generatriz que buscamos. Este vídeo de Sedgewick, sacado de un curso que imparte en Coursera, da suficientes detalles para hacerse una idea cabal de las posibilidades del método.

El «método simbólico» para obtener funciones generatrices no es más que la primera parte del libro. En la segunda emplea toda la artillería del análisis complejo para extraer información asintótica de la fórmula combinatoria en cuestión, partiendo directamente de la función generatriz. Hay dos técnicas básicas. La primera consiste en describir asintóticamente la función en las proximidades de su singularidad más cercana al origen y usar los coeficientes de su desarrollo como aproximación. La segunda consiste en aplicar el método de steepest descent a la fórmula integral de Cauchy de los coeficientes. Con estas dos técnicas, además, consigue clasificar problemas atendiendo a la forma de la función generatriz y encontrar una especie de clases de universalidad para los problemas combinatorios. La tercera parte (un solo capítulo de alrededor de cien páginas) aprovecha estas técnicas para obtener distribuciones de probabilidad a partir de fórmulas combinatorias.

No os voy a engañar: la segunda y terceras partes no son para «nenas». Son una masterpiece del análisis complejo y los métodos asintóticos, pero con frecuencia cuesta seguir los argumentos. No son imposibles de entender, pero sí que hay que emplearse a fondo. Prácticamente cada ejemplo está extraído de un artículo de investigación. Por contra, el catálogo de aplicaciones es tan enciclopédico que cuesta imaginarse alguna cuenta combinatoria que los autores no hayan realizado e incluido como un ejemplo en el libro. Éstas son, además, increíblemente variadas: árboles, permutaciones (claro), lenguajes formales, funciones, grafos, caminos aleatorios... Incluso, aprovechando el superpoder, resulta fácil dar la respuesta a curiosos acertijos (como el problema de los 100 presos, que también aparece en el libro). Más de 800 páginas de ars combinatoria y ars analytica.

¿Recomiendo leerlo? Bueno, vosotros mismos decidiréis cuando veáis el vídeo.