¿Números catalanes de mayor dimensión?

Question

Se podría imaginar la definición de varias nociones de números catalanes de dimensión superior, generalizando los objetos que cuentan. Por ejemplo, como los números catalanes cuentan las triangulaciones de polígonos convexos, se podrían contar las tetraederaciones de poliedros convexos, o más generalmente, triangulaciones de politopos. Quizás el número de triangulaciones de los $n$ -cubo son similares al catalán catalán? O, porque los números catalanes cuentan el número de caminos monótonos por debajo de la diagonal en un $n \times n$ se podría contar el número de trayectorias monótonas por debajo de el "hiperplano diagonal" en un $n \times \cdots \times n$ rejilla.

Me interesarían las referencias a tales generalizaciones, que seguramente se han considerado; sólo que no estoy buscando con la terminología adecuada. Estaría especialmente agradecido de conocer generalizaciones que compartan algo de la ubicuidad del número catalán. Gracias por las sugerencias.

Answer 1

Cuando se cuenta el número de caminos positivamente dirigidos desde $(0,0,\dots,0)$ a $(n,n,\dots,n)$ que se encuentran en la región $x_d\le x_1+\cdots+x_{d-1}$ puedes proyectar al plano $(x_d,x_1+\cdots+x_{d-1})$ y encontrará que necesita el número de trayectorias planas de $(0,0)$ a $(n,n(d-1))$ que se mantienen por encima de la línea $x=y$ y que tienen $n$ pasos verticales de cada color {1,...,d-1}. Así que la respuesta viene a ser $$\left(\binom{nd}{n}-\binom{nd}{n-1}\right)\binom{n(d-1)}{n,\dots,n}=\frac{n(d-2)+1}{n(d-1)+1}\frac{(nd)!}{(n!)^d}.$$ Ver también esta pregunta anterior para enumerar trayectorias reticulares por debajo de una línea.

Por otra parte, una forma de interpretar los números catalanes como caminos de celosía por debajo de la diagonal es considerarlos como el recuento del número de tablas estándar de Young de forma $(n,n)$ . Una generalización natural es, por ejemplo, el número de tablas estándar de Young de forma $(n,n,\dots,n)$ . Esto corresponde a la región $x_1\le x_2\le\cdots\le x_d$ y puede contarse utilizando la fórmula de la longitud del anzuelo. Véase mi respuesta aquí .

Answer 2

Lo más parecido que se me ocurre a lo que quieres es triangulaciones de politopos cíclicos pares. Son bonitas porque, a diferencia de las triangulaciones del cubo, todas utilizan el mismo número de símplices. Para más información, véase el artículo enlazado más arriba.

Hay otras generalizaciones importantes de los números catalanes, pero éstas son las únicas que yo llamaría particularmente de dimensión superior.

Answer 3

Dos documentos que abordan su pregunta de forma similar son:

(1) Categoría n libre generada por un cubo, matroides orientados y órdenes de Bruhat superiores de Karpranov y Voevodsky y

(2) Ordenaciones de hiperplanos, grupos de trenzas superiores y órdenes de Bruhat superiores por Manin y Schechtman

Mapas entre órdenes de Bruhat superiores y posets de Stasheff-Tamari superiores de H. Thomas sirve de continuación y completa algunos detalles, pero tiene un sabor diferente.

Brevemente, el documento (1) define (entre otras cosas) un poset $S(n,k), 0 \leq k \leq n$ con $|S(n,2)|$ igual al $n^{th}$ Número catalán. Los objetos de este poset se definen de 3 maneras (y se demuestra que son equivalentes): combinatoriamente (mediante politopos cíclicos), como "homotopías de homotopías" y como elementos de "la libre $(n-k)$ -categoría en el $n$ -simplex".

Así que si te gustan estas definiciones y crees que son naturales, $|S(n,k)|$ para $k >2$ te da números catalanes de "dimensión superior".

El documento (2) también hace algo bueno, pero no recuerdo qué.

Answer 4

Los números catalanes cuentan las tablas estándar de forma (n,n). Una forma de generalizar los números catalanes es considerar en su lugar los tableaux estándar de forma (n,n,n) dando los "números catalanes tridimensionales" y en general se pueden contar los tableaux estándar de forma (n,n,n,...,n)=(n^m).

Los números catalanes de dimensión superior me han surgido recientemente al estudiar un caso particular del fenómeno del cribado cíclico. El análogo q estándar de los números catalanes de dimensión superior forma polinomios que, cuando se evalúan en raíces primitivas de la unidad, cuentan el conjunto de puntos fijos de la acción del grupo cíclico generado por el "operador de promoción" en tableaux rectangulares.

Si le interesa, puede encontrar detalles al respecto en un artículo de Rhoades.

Rhoades,B. Tamizado cíclico, promoción y teoría de la representación. J. Combin. Theory Ser. A 117, 1 (2010),38-76.

Answer 5

Me interesan las secuencias anidadas de trayectorias Dyck. Giro tu imagen y pienso en un camino de Dyck como una secuencia de pasos $(1,1)$ y $(1,-1)$ que se mantiene por encima de $y=0$ . A secuencia anidada es una secuencia de $k$ trayectorias Dyck tales que si $1\le i<j\le k$ entonces el $i$ -th path nunca está por encima de el $j$ -camino. No conozco ninguna interpretación en términos de politopos.