Icke-korsande partition

Det finns 42 icke-korsande och 10 korsande partitioner i en uppsättning med 5 element

De 14 icke-korsande partitionerna i en 4-elementsuppsättning ordnade efter förfining i ett Hasse-diagram

I kombinatorisk matematik har ämnet icke-korsande partitioner antagit viss betydelse på grund av (bland annat) dess tillämpning på teorin om fri sannolikhet . Antalet icke-korsande partitioner av en uppsättning av n element är det n :te katalanska talet . Antalet icke-korsande partitioner av en n -elementuppsättning med k block finns i Narayanas taltriangel.

Definition

En partition av en mängd S är en uppsättning av icke-tomma, parvis disjunkta delmängder av S , kallade "delar" eller "block", vars förening är hela S . Betrakta en ändlig mängd som är linjärt ordnad, eller (motsvarande, för denna definitions syfte) arrangerad i en cyklisk ordning som hörnen på en vanlig n -gon. Ingen generalitet går förlorad genom att ta denna uppsättning till S = { 1, ..., n }. En icke-korsande partition av S är en partition där inga två block "korsar" varandra, dvs om a och b tillhör ett block och x och y till ett annat, är de inte ordnade i ordningen axby . Om man ritar en båge baserat på a och b , och en annan båge baserat på x och y , så korsar de två bågarna varandra om ordningen är axby men inte om det är axyb eller abxy . I de två senare ordningarna är partitionen { { a , b }, { x , y } } icke-korsande.

Korsning:	axby
Icke-korsande:	axyb
Icke-korsande:	abxy

På motsvarande sätt, om vi märker hörn av en regelbunden n -gon med siffrorna 1 till n , är de konvexa skroven av olika block av partitionen disjunkta från varandra, dvs de "korsar" inte heller varandra. Uppsättningen av alla icke-korsande partitioner av S betecknas ${\text{NC}}(S)$ . Det finns en uppenbar ordningsisomorfism mellan ${\text{NC}}(S_{1})$ och ${\text{NC}}(S_{2} )$ för två ändliga uppsättningar $S_{1},S_{2}$ med samma storlek. Det vill säga, ${\text{NC}}(S)$ beror i huvudsak bara på storleken på $S$ och vi betecknar med ${\text{NC }}(n)$ de icke-korsande partitionerna på valfri uppsättning av storlek n .

Gallerstruktur

Liksom uppsättningen av alla partitioner i uppsättningen { 1, ..., n }, är uppsättningen av alla icke-korsande partitioner ett gitter när den är delvis ordnad genom att säga att en finare partition är "mindre än" en grövre partition. Men även om det är en delmängd av gittret för alla partitioner, är det inte ett subgitter av gittret för alla partitioner, eftersom sammanfogningsoperationerna inte överensstämmer. Med andra ord, den finaste partitionen som är grövre än båda av två icke-korsande partitioner är inte alltid den finaste icke-korsande partitionen som är grövre än båda.

Till skillnad från gittret för alla partitioner i mängden, är gittret för alla icke-korsande partitioner i en mängd självdual, dvs. det är ordningsisomorft till gittret som är resultatet av att invertera den partiella ordningen ("vända upp och ner på den") . Detta kan ses genom att observera att varje icke-korsande partition har ett komplement. Faktum är att varje intervall inom detta gitter är självdual.

Roll i fri sannolikhetsteori

Gittret för icke-korsande partitioner spelar samma roll för att definiera fria kumulanter i fri sannolikhetsteori som spelas av gittret för alla partitioner för att definiera gemensamma kumulanter i klassisk sannolikhetsteori . För att vara mer exakt, låt $({\mathcal {A}},\phi )$ vara ett icke-kommutativt sannolikhetsutrymme (se fri sannolikhet för terminologi.), $a \in {\mathcal {A}}$ en icke-kommutativ slumpvariabel med fria kumulanter $(k_{n})_{n\in \mathbb {N} }$ . Sedan

$\phi (a^{n})=\summa _{\pi \in {\text{NC}} (n)}\prod _{j}k_{j}^{N_{j}(\pi )}$

där $N_{j}(\pi )$ anger antalet block med längden $j$ i den icke-korsande partitionen $\pi$ . Det vill säga, momenten för en icke-kommutativ slumpvariabel kan uttryckas som summan av fria kumulanter över summan av icke-korsande partitioner. Detta är den fria analogen till momentkumulantformeln i klassisk sannolikhet. Se även Wigner halvcirkelfördelning .

• Germain Kreweras, "Sur les partitions non croisées d'un cycle", Discrete Mathematics , volym 1, nummer 4, sidorna 333–350, 1972.
• Rodica Simion , "Noncrossing partitions", Discrete Mathematics , volym 217, nummer 1–3, sidorna 367–409, april 2000.
• Roland Speicher, "Fri sannolikhet och icke-korsande partitioner" , Séminaire Lotharingien de Combinatoire , B39c (1997), 38 sidor, 1997