En matemática combinatoria , el tema de las particiones no cruzadas ha adquirido cierta importancia debido (entre otras cosas) a su aplicación a la teoría de la probabilidad libre . El número de particiones no cruzadas de un conjunto de n elementos es el n- ésimo número catalán . El número de particiones que no se cruzan de un conjunto de n elementos con k bloques se encuentra en el triángulo numérico de Narayana .
Definición
Una partición de un conjunto S es un conjunto de no vacíos, subconjuntos disjuntos de pairwise S , llamado "partes" o "bloques", cuya unión es todo de S . Considere un conjunto finito que está ordenado linealmente, o (de manera equivalente, para los propósitos de esta definición) dispuesto en un orden cíclico como los vértices de un n -gon regular . No se pierde ninguna generalidad al tomar este conjunto como S = {1, ..., n }. Una partición noncrossing de S es una partición en la que no hay dos bloques de "cruz" entre sí, es decir, si una y b pertenecen a un bloque y x y y a otro, no están dispuestos en el orden AxBy . Si uno dibuja un arco basado en un y b , y otro arco basan en x y y , a continuación, los dos arcos se cruzan entre sí si la orden es AxBy pero no si es axyb o abxy . En los dos últimos órdenes, la partición {{ a , b }, { x , y }} no se cruza.
Cruce: | axby |
No cruzado: | axyb |
No cruzado: | abxy |
De manera equivalente, si etiquetamos los vértices de un n -gon regular con los números del 1 al n , los cascos convexos de los diferentes bloques de la partición están separados entre sí, es decir, tampoco se "cruzan" entre sí. El conjunto de todas las particiones de S que no se cruzan se denota. Hay un isomorfismo de orden obvio entre y para dos conjuntos finitos con el mismo tamaño. Es decir, depende esencialmente sólo del tamaño de y denotamos por las particiones que no se cruzan en cualquier conjunto de tamaño n .
Estructura de celosía
Como el conjunto de todas las particiones del conjunto {1, ..., n }, el conjunto de todas las particiones que no se cruzan es un enrejado cuando se ordena parcialmente diciendo que una partición más fina es "menor que" una partición más gruesa. Sin embargo, a pesar de que es un subconjunto de la red de todas las particiones, es no una subred de la red de todas las particiones, ya que la unen a las operaciones no están de acuerdo. En otras palabras, la partición más fina que es más gruesa que las dos particiones no cruzadas no siempre es la partición no cruzada más fina que es más gruesa que ambas.
A diferencia de la celosía de todas las particiones del conjunto, la celosía de todas las particiones que no se cruzan de un conjunto es auto-dual, es decir, es de orden isomórfico a la celosía que resulta de invertir el orden parcial ("darle la vuelta") . Esto se puede ver observando que cada partición que no se cruza tiene un complemento. De hecho, cada intervalo dentro de esta red es auto-dual.
Papel en la teoría de la probabilidad libre
El enrejado de particiones que no se cruzan juega el mismo papel en la definición de acumuladores libres en la teoría de la probabilidad libre que desempeña el enrejado de todas las particiones en la definición de acumuladores conjuntos en la teoría clásica de la probabilidad . Para ser más precisos, dejemosser un espacio de probabilidad no conmutativo (Ver probabilidad libre para la terminología),una variable aleatoria no conmutativa con acumulados libres. Luego
dónde denota el número de bloques de longitud en la partición que no se cruza . Es decir, los momentos de una variable aleatoria no conmutativa se pueden expresar como una suma de acumulados libres sobre la suma de particiones que no se cruzan. Este es el análogo libre de la fórmula de momento acumulativo en probabilidad clásica. Consulte también Distribución de semicírculo de Wigner .
Referencias
- Germain Kreweras, "Sur les partitions non croisées d'un cycle", Discrete Mathematics , volumen 1, número 4, páginas 333–350, 1972.
- Rodica Simion , "Noncrossing particitions", Discrete Mathematics , volumen 217, números 1–3, páginas 367–409, abril de 2000.
- Roland Speicher, "Probabilidad libre y particiones no cruzadas" , Séminaire Lotharingien de Combinatoire , B39c (1997), 38 páginas, 1997