Particiones no cruzadas

Question

Una partición establecida no se cruza si siempre que cuatro elementos $a<b<c<d$ son tales que $a,c$ están en el mismo bloque y $b,d$ están en el mismo bloque entonces $a,b,c,d$ están todos en el mismo bloque.

¿Puedo obtener una lista de particiones de conjuntos que no se cruzan?

Con "Combinatorica" ​​puedo obtener TODAS las particiones establecidas (digamos de {1,2,3,4}) con el comando SetPartitions [4].

Lo que quiero es esta lista sin el elemento {{1,3}, {2,4}} que no es no cruzado.

Answer 1

Needs["Combinatorica`"]

ClearAll[nonCrossingSetPartitions]
nonCrossingSetPartitions = 
    DeleteCases[{___, {___, a_, ___, c_, ___}, ___, {___, b_, ___, d_, ___}, ___} /;
       a < b < c < d] @* SetPartitions;

nonCrossingSetPartitions @ 4 // Column

nonCrossingSetPartitions @ 5 // Length

42

Answer 2

Tengo un paquete de Mathematica para generar objetos catalanes en GitHub, así que tengo un algoritmo recursivo que genera lo que quieres. Además, tiene una bonita representación gráfica de estos y algunas operaciones sobre estos, como la rotación.

Simplemente descargue el paquete y haga

Needs["CatalanObjects`"]
Last /@ NonCrossingPartitions[4]

Llegar

{{{1, 2, 3, 4}}, {{3}, {1, 2, 4}}, {{2}, {1, 3, 4}}, {{1, 4}, {2, 
   3}}, {{2}, {3}, {1, 4}}, {{1}, {2, 3, 4}}, {{1}, {3}, {2, 4}}, {{1,
    2}, {3, 4}}, {{1}, {2}, {3, 4}}, {{4}, {1, 2, 3}}, {{2}, {4}, {1, 
   3}}, {{1}, {4}, {2, 3}}, {{3}, {4}, {1, 2}}, {{1}, {2}, {3}, {4}}}

Si no quiere todo en el paquete, debería ser fácil extraer el método.