En matemáticas combinatorias , 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 de Catalan . El número de particiones no cruzadas de un conjunto de n elementos con k bloques se encuentra en el triángulo numérico de Narayana .
Una partición de un conjunto S es un conjunto de subconjuntos no vacíos, disjuntos por pares de S , llamados "partes" o "bloques", cuya unión es todo S . Considérese un conjunto finito que está ordenado linealmente, o (equivalentemente, para los propósitos de esta definición) dispuesto en un orden cíclico como los vértices de un n -gono regular . No se pierde ninguna generalidad al tomar este conjunto como S = { 1, ..., n }. Una partición sin cruce de S es una partición en la que no hay dos bloques que se "crucen" entre sí, es decir, si a y b pertenecen a un bloque y x e y a otro, no están dispuestos en el orden axby . Si uno dibuja un arco basado en a y b , y otro arco basado en x e y , entonces los dos arcos se cruzan entre sí si el orden es axby pero no si es axyb o abxy . En los dos últimos órdenes la partición { { a , b }, { x , y } } no es cruzada.
De manera equivalente, si etiquetamos los vértices de un n -gono regular con los números 1 a n , las envolturas convexas de diferentes bloques de la partición son disjuntas entre sí, es decir, tampoco se "cruzan" entre sí. El conjunto de todas las particiones no cruzadas de S se denota . Hay un isomorfismo de orden obvio entre y para dos conjuntos finitos con el mismo tamaño. Es decir, depende esencialmente solo del tamaño de y denotamos por las particiones no cruzadas en cualquier conjunto de tamaño n .
Al igual que el conjunto de todas las particiones del conjunto { 1, ..., n }, el conjunto de todas las particiones que no se cruzan es una red cuando se ordena parcialmente diciendo que una partición más fina es "menor que" una partición más gruesa. Sin embargo, aunque es un subconjunto de la red de todas las particiones del conjunto, no es una subred, porque el subconjunto no está cerrado bajo la operación de unión en la red más grande. En otras palabras, la partición más fina que es más gruesa que ambas de dos particiones que no se cruzan no siempre es la partición más fina que no se cruza que es más gruesa que ambas.
A diferencia de la red de todas las particiones del conjunto, la red de todas las particiones que no se cruzan es autodual, es decir, es isomorfa en orden a la red 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 que no se cruza. De hecho, cada intervalo dentro de esta red es autodual.
La red de particiones que no se cruzan desempeña el mismo papel en la definición de cumulantes libres en la teoría de probabilidad libre que el que desempeña la red de todas las particiones en la definición de cumulantes conjuntos en la teoría de probabilidad clásica . Para ser más precisos, sea un espacio de probabilidad no conmutativo (ver probabilidad libre para la terminología), una variable aleatoria no conmutativa con cumulantes libres . Entonces
donde denota el número de bloques de longitud en la partición no cruzada . Es decir, los momentos de una variable aleatoria no conmutativa se pueden expresar como una suma de cumulantes libres sobre la suma de particiones no cruzadas. Este es el análogo libre de la fórmula momento-cumulante en probabilidad clásica. Véase también distribución de semicírculo de Wigner .
