Egy együttes felosztása

A partíció egy sor X gyűjteménye részei nem kiüríteni az X páronként diszjunkt , és akinek unió az X .

Meghatározás

Legyen X halmaz . Egy sor részei X partíciója X , ha:

• e részek egyike sem üres;
• egyesülésük egyenlő X-szel  ;
• ketten-ketten szét vannak választva.

Példák

Az {1, 2, 3} halmaz a következő partíciókat tartalmazza:

• {{1}, {2}, {3}};
• {{1, 2}, {3}};
• {{1, 3}, {2}};
• {{1}, {2, 3}};
• és {{1, 2, 3}}.

Vegye figyelembe, hogy:

• Az {∅, {1, 3}, {2}} nem partíció, mert az üres set halmazt tartalmazza;
• Az {{1, 2}, {2, 3}} nem pontszám, mert a 2. elem több részhez tartozik;
• A {{1}, {2}} nem része az {1, 2, 3} partícióinak, mert az összes elem egyesítése {1, 2}; ez az {1, 2} partíciója.

Abban az esetben, ha a pontszám összes elemének azonos a kardinalitása, megtaláljuk a pásztorok lemmáját .

Az üres partíció az üres halmaz partíciója (ráadásul ez az egyetlen), mivel minden elemének (nincs ilyen) minden kívánatos tulajdonsága megvan (itt: hogy ne legyen üres és ne legyen szét), és hogy az egyesülésük üres ( definíció szerint ).

Partíciók és ekvivalencia relációk

Ha ekvivalencia reláció van megadva az X halmazon , akkor az összes ekvivalencia osztály halmaza alkotja az X partícióját . Ezzel szemben, ha egy partíció a P a X adott, akkor meg tudjuk határozni egy ekvivalencia reláció X jelöljük ~, a x ~ y , ha, és csak akkor, ha létezik, elemei között P , egy része a X , amely tartalmazza mindkét X és y . Az ekvivalencia-reláció és a partíció fogalma tehát alapvetően egyenértékű.

Részleges rend a partíciókon

A szett összes partícióját nem üres halmaz X jelentése részben rendezett  : definíció, egy partíciót finomabb, mint a másik , ha osztja az elemek a többi kisebb részekre. Ez a részleges érdekében alkot komplett rácsos , amely a legkisebb eleme (a legkisebb bírság partíció) a durva partíció egyik részében ( X ) és a legnagyobb (a legvékonyabb partíció) a partíció egyesterhességek .

Partíciók száma egy véges halmazban

A Bell szám , B n , egy n elemkészlet partícióinak száma .

Az n megkülönböztethetetlen elemet tartalmazó halmaz különböző partícióinak száma az egész szám partícióinak száma .

Pontosan k részhalmazba sorolt partícióinak száma a második típusú S ( n , k ) Stirling-száma .

Páros kotta

• Egy 2 n elemű halmaz páros partícióinak száma egyenlő (2 n )! / (2 n n !).
• Bármely végtelen halmaz legalább egy partíciót beenged páronként (ha feltételezzük, hogy a választott axióma igaz ).