8 votos

Las especies combinatorias, el significado y los problemas pueden resolverse con ella.

Especies combinatorias es un tema con el que me he topado recientemente cuando, por curiosidad, he buscado una posible interacción entre la teoría de categorías y la combinatoria. Después de un rato terminé aquí Aprendizaje de especies combinatorias. y más tarde a este libro Especies combinatorias y estructuras arborescentes . Para alguien que se sienta cómodo en la Teoría de Categorías, esto puede ser algo muy bonito sobre lo que reflexionar y crea una flexibilidad también para la teoría de las funciones generadoras, y esto último tiene un significado importante.

Aunque, en cualquier instancia de libro / notas que puedo llegar, no encontrar una aplicación "intuitiva" de las especies combinatoria. Combinatoria, definitivamente no se trata de contar más, pero podría decirse que alguien declara que las cosas más divertidas en ella tiene que ver con problemas de conteo (porque ese tipo de problemas tienen más intuición supongo).

Así que mi pregunta tiene que ver con eso; ¿Podría darme por favor un ejemplo de aplicación de Especies Combinatorias en combinatoria Enumerativa? Cualquier otro ejemplo de aplicación también es bienvenido, por supuesto.

Último comentario: No tengo problema con ello por su definición o significado. Busco un enfoque intuitivo de la noción mencionada (He mencionado esto último, porque quiero evitar cualquier posible duplicación con otras preguntas posiblemente relacionadas en MSE, porque creo que las he comprobado todas y no ha aparecido ninguna respuesta/pregunta de este tipo. Si existe tal duplicación con una respuesta, por favor, no dude en mencionarlo).

Gracias.

0 votos

¿En qué sentido no son "intuitivos" los numerosos ejemplos de "Especies combinatorias y estructuras arborescentes"? ¿Cómo sería una aplicación "intuitiva"? ¿O quiere aplicaciones fuera de la combinatoria?

0 votos

Derek gracias por tu respuesta, una aplicación fuera de la combinatoria sería genial si te enteras. Aunque, principalmente el libro presenta el montaje y la maquinaria de toda la teoría. Así que estoy buscando alguna intuición. Digamos, si quiero explicar a alguien undergrad, ¿cuál es la mejor manera de hacerlo así? Si conocéis algún ejemplo dentro del libro que lo muestre, hacédmelo saber porque probablemente me lo he saltado accidentalmente.

6voto

T. Gunn Puntos 1203

Uno de los primeros resultados es proporcionar una prueba de Fórmula de Cayley para el número de árboles en $\{1,\dots,n\}$ . Para ello $\mathcal{T}$ sea la clase de los árboles. Entonces $\frac{d}{ds}\mathcal{T}$ es la clase de árboles con un vértice eliminado. Se trata de una colección desordenada de árboles más pequeños con un vértice distinguido (el que estaba unido al vértice que hemos eliminado). Así,

$$ \frac{d}{ds} \mathcal{T} \leftrightarrow \mathcal{E}\left( \frac{sd}{ds}\mathcal{T} \right). $$

(Aquí $\mathcal{E}(X) = \{X\}$ para que $|\mathcal{E}(\{1,\dots,n\})| = 1$ para todos $n$ .)

En términos de funciones generadoras, esto dice

$$ T'(x) = \exp\left(x T'(X) \right). $$

Si hacemos la sustitución $A(x) = xT'(x)$ entonces esto dice

$$ A(x) = x \exp A(x). $$

Aplicar ahora Inversión de Lagrange-Bürmann para obtener

$$ \begin{align*} \text{# of trees on $n$ vertices} &= \left[ \frac{x^n}{n!} \right] T(x) \\ &= \frac{1}{n} \left[ \frac{x^{n}}{n!} \right] A(x) \\ &= \frac{1}{n} \left[ \frac{u^{n - 1}}{(n - 1)!} \right] \exp(n u) \\ &= \frac{1}{n} n^{n - 1} \\ &= n^{n - 2}. \end{align*} $$


Esto es bastante básico. Lo más impresionante es que esta técnica puede demostrar la inversión de Lagrange-Bürmann. Veamos un enunciado del teorema:

Sea $K$ sea un anillo conmutativo que contenga los racionales. Sea $F, G \in K[[u]]$ sean series formales y supongamos $G$ tiene un término constante distinto de cero (no necesariamente invertible).

Entonces la fórmula $R(x) = xG(R(x))$ tiene una solución única (distinta de cero) en $K[[x]]$ .

Los coeficientes de $F(R(x))$ vienen dadas por $$ \left[ \frac{x^n}{n!} \right] F(R(x)) = \left[ \frac{u^{n-1}}{(n - 1)!} \right] F'(u)G(u)^n. $$

En particular, $$ \left[ \frac{x^n}{n!} \right] R(x) = \left[ \frac{u^{n-1}}{(n - 1)!} \right] G(u)^n. $$

Para ello, deje que $\mathcal{G}$ ser la clase "genérica $\mathcal{E}$ con pesos $g_n$ en conjuntos de tamaño $n$ . Entonces $\mathcal{F}$ sea la clase "genérica" con pesos $f_n$ .

Recordemos la descomposición que hicimos para los árboles:

$$ \frac{sd}{ds} \mathcal{T} \leftrightarrow \mathcal{X} * \mathcal{E}\left( \frac{sd}{ds} \mathcal{T} \right) $$

donde he introducido un factor de $\mathcal{X}$ en ambos lados (la función generadora de $\mathcal{X}$ es sólo $x$ por cierto). Esta es la descomposición para árboles con raíces . Por lo tanto

$$ \mathcal{R} \leftrightarrow \mathcal{X} * \mathcal{G}(\mathcal{R}) $$

define una recurrencia para árboles con raíces ponderadas. En consecuencia, debe existir una función generadora única $R(x)$ que satisfaga esta recurrencia.

Siguiente, $$ \mathcal{F}(\mathcal{R}) $$ es la especie de $f_n$ -bosques ponderados de $g_n$ -árboles con raíces ponderadas. Dejando, $N = \{1,\dots,n\}$ . La fórmula del coeficiente dice que

$$ \#\left(\frac{sd}{ds} \mathcal{F}(\mathcal{R}) \right)(N) = \# \left( \frac{sd}{ds}\mathcal{F} * \mathcal G^n \right)(N). $$

Hay factores adicionales añadidos a ambos lados para que sea posible establecer una biyección ponderada. Desgraciadamente ocuparía demasiado espacio describir esta bijección. En cualquier caso, esa bijección te da una prueba combinatoria de la fórmula de Lagrange-Bürmann.

0 votos

T. Gunn, gracias por su tiempo y por la larga respuesta. Tengo que leerla detenidamente, así que probablemente vuelva más tarde.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X