Partitions non croisées

Question

Une partition d'ensemble est non croisée si chaque fois que quatre éléments $a<b<c<d$ sont tels que $a,c$ sont dans le même bloc et $b,d$ sont dans le même bloc alors $a,b,c,d$ sont tous dans le même bloc.

Puis-je obtenir une liste de partitions d'ensemble non croisées.

Avec "Combinatorica", je peux obtenir TOUTES les partitions définies (par exemple {1,2,3,4}) avec la commande SetPartitions [4].

Ce que je veux, c'est cette liste sans l'élément {{1,3}, {2,4}} qui n'est pas non croisé.

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

J'ai un package Mathematica pour générer des objets catalans sur GitHub, donc j'ai un algorithme récursif qui génère ce que vous voulez. De plus, il a une belle représentation graphique de ceux-ci, et certaines opérations sur ceux-ci, telles que la rotation.

Téléchargez simplement le package et faites

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

obtenir

{{{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 vous ne voulez pas que tout soit contenu dans le package, il devrait être facile d'extraire la méthode.