El catalán números de $C_n$ recuento tanto
- el Dyck caminos de longitud $2n$, y
- los métodos para asociar $n$ aplicaciones repetidas de una operación binaria.
Llamamos a la última magma expresiones; vamos a explicar a continuación.
Dyck caminos, y su estructura de celosía
Un Dyck camino de la longitud de la $2n$ es una secuencia de $n$ arriba y a la derecha los trazos y $n$ hacia abajo y a la derecha los trazos, todos con la misma longitud, de tal manera que la secuencia comienza y termina en la misma línea horizontal y nunca pasa por debajo de ella. Una foto de los cinco longitud-6 Dyck caminos se muestra aquí:
A: B: C: D: E:
/\
/ \ /\/\ /\ /\
/ \ / \ / \/\ /\/ \ /\/\/\
Hay una orden de la relación en el conjunto de la longitud-$2n$ Dyck caminos: $P\leq Q$ si $P$ se adapta completamente bajo $Q$; voy a llamar a la altura de la orden, a pesar de que en el título del post, que yo he llamado "Dyck orden". Me han dicho que debería ser llamado Stanley el entramado de la orden. Para $n=3$ da la siguiente celosía:
A
|
B
/ \
C D
\ /
E
Para cualquier $n$, se obtiene un poset estructura en el conjunto de la longitud-$2n$ Dyck rutas utilizando la altura de la orden, y de hecho este poset siempre es un álgebra de Heyting (que representa el subobjeto clasificador para el topos de presheaves en el trenzado de flecha categoría de $\mathbb{N}$, la libre monoid en un generador de ver este mathoverflow pregunta).
El Magma y las expresiones de la "exponencial de la orden de evaluación"
Un conjunto con una operación binaria, decir •, se llama magma. Por un magma de la expresión de la longitud de la $n$, nos referimos a una manera de asociar $n$ aplicaciones repetidas de la operación. Aquí están los cinco magma expresiones de longitud 3:
A: B: C: D: E:
a•(b•(c•d)) a•((b•c)•d) (a•b)•(c•d) (a•(b•c))•d ((a•b)•c)•d
Es bien conocido que el conjunto de la longitud-$n$ magma expresiones tiene la misma cardinalidad que el conjunto de la longitud-$2n$ Dyck caminos: son representaciones de la $n$th catalán número.
Una ordenó el magma es un magma cuyo subyacente esté equipado con un orden parcial, y cuyo funcionamiento se conserva el orden en ambas variables. Dado un orden de magma $(A,$•$,\leq)$, y el magma expresiones $E(a_1,\ldots,a_n)$ e $F(a_1,\ldots,a_n)$, escribir $E\leq F$ si la desigualdad se cumple para cada elección de $a_1,\ldots,a_n\in A$. Llamamos a esto el orden de evaluación.
Deje $P=\mathbb{N}_{\geq 2}$ ser el conjunto de los números naturales con números cardinales al menos 2, la forma logarítmica positivo números naturales. Equipado con la operación dada por la exponenciación, $c$•$d\:=c^d$, se obtiene un orden de magma, utilizando la usual $\leq$-orden. De hecho, si $2\leq a\leq b$ e $2\leq c\leq d$ entonces $a^c\leq b^d$.
Pregunta: Es la exponencial de la orden de evaluación en longitud-$n$ expresiones en la orden de magma $(P,$^$,\leq)$ isomorfo a la altura de la orden de la longitud-$2n$ Dyck caminos?
Que yo sepa no hay un a priori de la razón para pensar que la respuesta a la anterior pregunta debe ser afirmativa. Un categórico enfoque podría ser la de pensar de los elementos de $P$ como conjuntos de dos elementos especiales, y el uso de ellas para definir inyectiva de funciones entre los Hom-establece, por ejemplo, un mapa $$\mathsf{Hom}(c,\mathsf{Hom}(b,a))\to\mathsf{Hom}(\mathsf{Hom}(c,b),a).$$ Sin embargo, mientras yo pueda definir el mapa de arriba, no estoy seguro de cómo generalizar es. Y a la inversa, que es comparable en la exponencial de la orden de evaluación significa que uno puede definir un único inyectiva mapa entre hom-conjuntos, no es evidente para mí en absoluto.
Sin embargo, a pesar del hecho de que no sé dónde buscar para una prueba, tengo evidencia para presentar en favor de una respuesta afirmativa a la pregunta anterior.
La evidencia de que las órdenes de acuerdo
Es fácil comprobar que para $n=3$, estos dos órdenes de acuerdo:
a^(b^(c^d)) A := A(a,b,c,d)
| |
a^((b^c)^d) B
/ \ / \
(a^b)^(c^d) (a^(b^c))^d C D
\ / \ /
((a^b)^c)^d E
Esto puede ser visto por tomar los registros de cada expresión. (Para ver que C y D son incomparables: use a=b=c=2 y d=grande para obtener el C>D; y el uso de a=b=d=2 y c=grande para obtener D>C.) por Lo tanto el orden de evaluación en longitud-3 expresiones en $(P,$^$,\leq)$ está de acuerdo con la altura de la orden de la longitud de la $6$ Dyck caminos.
(Tenga en cuenta que la respuesta a la pregunta sería negativo si usamos $\mathbb{N}$ o $\mathbb{N}_{\geq 1}$ en lugar de $P=\mathbb{N}_{\geq2}$ como en la citada pregunta. De hecho, con $a=c=d=2$ e $b=1$, tendríamos $A(a,b,c,d)=2\leq 16=E(a,b,c,d)$.)
Es incluso más fácil de ver que las órdenes de acuerdo en el caso de $n=0,1$, cada uno de los cuales tiene un solo elemento, y en el caso de $n=2$, donde el orden de $(a^b)^c\leq a^{(b^c)}$ no muy sorprendentemente coincide con el de longitud-4 Dyck caminos:
/\
/\/\ ≤ / \
De hecho, el orden-isomorfismo de $n=2$ no es de extrañar, porque sólo hay dos posibles parcial de las órdenes en un conjunto con dos elementos. Sin embargo, de acuerdo a la OEIS, hay 1338193159771 diferentes parcial de las órdenes en un conjunto con $C_4=14$ elementos. Así que sin duda, sería sorprendente si el orden de evaluación para la longitud-4 expresiones en $(P,$^$,\leq)$ fueron para que coincida con la altura de la orden de la longitud-8 Dyck caminos. Pero después de algunos tediosos cálculos, he convencido a mí misma de que estos dos órdenes, de hecho, de acuerdo para $n=4$! Por supuesto, esto podría ser una coincidencia, pero sin duda es una llamativa.
Los pensamientos?
