La combinatoria de plazo álgebras de

Question

Mi pregunta es sobre el número de términos de tamaño de la $n$ en el plazo de álgebras de un arbitrario (finito) de la firma.

Una firma es un mapa de $\Sigma : S \rightarrow \mathbb{N}$ a partir de un conjunto $S$ de símbolos. Asumimos $S$ a un ser finito, y $\mathbb{N}$ a contener 0. Si $\Sigma(f) = n$ nos dicen que $f$ ha arity $n$. Llamamos símbolos con arity 0 constantes.

Aquí están algunos ejemplos de las firmas.

• $\Sigma_G$, la firma de los grupos, se basa en los símbolos $+, -$ y $0$ con los siguientes arities. $\Sigma_G(+) = 2$, $\Sigma_G(-) = 1$, and $\Sigma_G(e) = 0$.
• $\Sigma_L$, la firma de limitada celosías, ha símbolos $\vee$, $\wedge$, $0$ y $1$, con arities $\Sigma_L(\vee) = 2$, $\Sigma_L(\wedge) = 2$, $\Sigma_L(0) = 0$ y $\Sigma_L(1) = 0$.
• $\Sigma_F$, la firma de los campos, ha símbolos $+, -, 0, \cdot, ^{-1}$ and $1$, with arities $\Sigma_F(+) = 2$, $\Sigma_F(\cdot) = 2$, $\Sigma_F(-) = 1$, y $\Sigma_F(-) = 1$, $\Sigma_F(0) = 0$ $\Sigma_F(1) = 0$.

El término álgebra sobre un conjunto de variables $X$ se denota $\Sigma(X)$. Es inductiva generada por las reglas siguientes.

• Si $x \in X$, $x$ es un miembro de $\Sigma(X)$.
• Si $f \in \Sigma(n)$$t_1, ..., t_n \in \Sigma(X)$, luego también se $f(t_1, ..., t_n) \in \Sigma(X)$.

Ejemplos de términos en el álgebra $\Sigma_G(\{x, y, z\})$ de estos grupos incluyen a $-(x+(y + z))$$-0$. Estos son también los términos de $\Sigma_F(\{x, y, z\})$. El plazo $0 \wedge (1 \vee 0)$ está en $\Sigma_L(\emptyset)$.

Podemos definir la noción usual de tamaño de los términos de la siguiente manera. $$ \mathsf{tamaño}(f(t_1, ..., t_n)) = 1 + \sum_{i=1}^n \mathsf{tamaño}(t_i) \qquad\qquad \mathsf{tamaño}(c) = 1 $$ Aquí $c$ rangos de las constantes en $\Sigma$, e $f \in \Sigma(n)$.

Con esta noción de tamaño, $0 \wedge (1 \vee 0)$, por ejemplo, tiene el tamaño de 5, mientras que $-0$ tiene tamaño 2.

Ahora podemos hacer preguntas como: ¿cuántos elementos de tamaño $n$ aparece el término álgebra $\Sigma(\emptyset)$ contienen?

Considere la posibilidad de una firma de $\Sigma$ con símbolos $\{+, 0\}$ tal que $\Sigma(+) = 2$ $\Sigma(0) = 0$ . Deje $C'_n$ el número de términos en $\Sigma(\emptyset)$ del tamaño de la $n$. La secuencia de $C'_n$ comienza de la siguiente manera. $$ 0, 1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42, 0, 132, 0, 429, 0, 1430, 0, 4862 $$ La no-cero larga corresponde exactamente a la Catalán números de $C_n$ que se define por la siguiente ecuación recursiva. $$ C_0 = 1 \qquad\qquad C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i} $$

La secuencia de números de términos en $\Sigma_G(\emptyset)$, plazo de álgebra de grupos con ninguna de las variables comienza con los siguientes números. $$ 0, 1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634 $$

No es demasiado difícil trabajar fuera de la ecuación recursiva de dar el número de términos de tamaño de la $n$ arbitrarias de firmas (es una generalización de la recursividad a la catalana, números, utilizando entero de particiones).

Pregunta. Sin duda, este problema debe contar han sido investigados, pero mi google ha no busque nada relevante. Yo estaría encantado de aprender acerca de los libros o documentos que considere la posibilidad de este problema. Estoy especialmente interesado en formas cerradas, en el caso de que existan y aproximaciones.

Answer 1

Permítanme describir una reformulación del problema en un lenguaje más familiar para mí. La pregunta es contar el número de (arraigada, planar) árboles con $n$ nodos (esto está de acuerdo con sus ejemplos sobre el tamaño, pero no con su definición) con las siguientes propiedades:

• Cada nodo se etiqueta con un elemento de $S$.
• Si un nodo se etiqueta por $s \in S$, entonces se ha $\Sigma(s)$ niños.

Deje $t_n$ denotar el número de estos árboles. La clave para la comprensión de esta cuestión es el uso de funciones de generación, y en lugar de simplemente el estudio de la secuencia de $t_n$ que el estudio de la función $$T(z) = \sum_{n \ge 0} t_n z^n.$$

La definición recursiva de los términos conduce a una relación satisfecho por $T$. Más precisamente, vamos a $s_i$ el número de símbolos con arity $i$. Entonces yo reclamo que $$T = z \sum_{i \ge 0} s_i T^i.$$

Esta relación puede ser entendido de forma combinatoria de la siguiente manera: se divide el conjunto de árboles basados en la arity de sus raíces. Si el arity es $i$, entonces el árbol consiste en una de las $s_i$ posible raíces junto con $i$ otros árboles de la misma forma. La expansión de la de arriba da una recursividad para $t_n$, pero es más para trabajar directamente con los de arriba en su lugar.

En el ejemplo que nos ha $s_0 = s_2 = 1$ y todas las demás condiciones iguales a cero, dando $$T = z (1 + T^2) \Rightarrow T = \frac{1 - \sqrt{1 - 4z^2}}{2z}$$

que es una de las funciones de generación de los números de catalán. En general, por Lagrange de la inversión que hemos $$t_n = \frac{1}{n} [w^n] \left( \sum s_i w^i \right)^n$$

donde $[w^n]$ denota el coeficiente de $w^n$.

N. B.: no es necesario para $S$ a un ser finito; la única condición para que este problema tiene una respuesta es que hay sólo un número finito de símbolos de un determinado arity y al menos un símbolo de arity $0$. Por ejemplo, considere el caso en que $s_i = 1$ todos los $i$. Esto le da $$T = z(1 + T + T^2 + ...) = \frac{z}{1 - T} \Rightarrow T - T^2 = z \Rightarrow T = \frac{1 - \sqrt{1 - 4z}}{2}$$

que es otra generación de función para el catalán números.

Algunas sugerencias para la lectura adicional, aproximadamente en orden de dificultad:

• Wilf del generatingfunctionology (disponible gratuitamente en internet)
• Flajolet y Sedgewick de la Analítica de la Combinatoria (también disponible gratuitamente en internet)
• Stanley Combinatoria Enumerativa, Vol. II
• Bergeron, Labelle, y Leroux de la Combinatoria de las Especies y las Estructuras en Árbol

Un último comentario. Puede que no sea obvio como para demostrar rigurosamente que los coeficientes de $T$ se determina únicamente por una relación de la forma $T = z \sum s_i T^i$. Uno puede hacer esto mediante la inducción, pero la forma más limpia sé cómo hacerlo es la apelación a la Banach teorema de punto fijo. $T$ es un punto fijo del mapa $$f \mapsto z \sum s_i f^i$$

actuando en el espacio de poder formal de la serie de $\mathbb{R}[[z]]$. Este espacio está equipado con una norma $$|f| = 2^{-n}$$

donde$f = a_n x^n + \text{higher terms}$$a_n \neq 0$, y en el hecho de que está completa relativa a la inducida por la métrica (ejercicio). El mapa de $f \mapsto z \sum s_i f^i$ es una contracción, por lo que tiene un único punto fijo. De hecho, esta es una prueba totalmente constructiva: a partir de cualquier inicial $T_0$, se puede considerar que la secuencia de $$T_n = z \sum s_i T_{n-1}^i$$

y esta secuencia de alimentación de la serie convergerá a $T$ en el sentido de que los coeficientes de estabilizar a los coeficientes de $T$. Comenzando con $T_0 = 0$ corresponde a contando los árboles de la forma anterior, pero de limitada profundidad.