Partition av en mängd

För andra betydelser, se partition.

En partition, eller klassindelning av en mängd är en uppdelning av mängden i delar som inte överlappar och som tillsammans omfattar hela mängden.

Formell definition

En partition av en mängd ${\displaystyle M}$ är en mängd som består av icke-tomma delmängder till ${\displaystyle M}$ sådan att varje element i ${\displaystyle M}$ tillhör en och endast en av dessa delmängder.

Detta kan formuleras ekvivalent som att ${\displaystyle P}$ är en partition av ${\displaystyle M}$ om:

• Unionen av alla element i ${\displaystyle P}$ är lika med ${\displaystyle M}$ (${\displaystyle P}$ täcker ${\displaystyle M}$).
• Varje snitt av två element i ${\displaystyle P}$ är tomt. (Elementen i ${\displaystyle P}$ är disjunkta).

Detta kan skrivas symboliskt:

• ${\displaystyle \bigcup _{A\in P}A=M}$
• ${\displaystyle A\cap B=\emptyset ~~\forall A,B\in P:A\neq B}$.

Notera alltså att elementen i ${\displaystyle P}$ inte kallas partitioner, utan ${\displaystyle P}$ kallas partition.

Exempel

• En mängd innehållande ett element, ${\displaystyle \{x\}}$ kan partitioneras på ett sätt: ${\displaystyle \{\{x\}\}}$.
• En partitionering av ${\displaystyle \{1,2,3\}}$ är ${\displaystyle \{\{1\},\{2,3\}\}}$, en annan är ${\displaystyle \{\{1,2\},\{3\}\}}$.
• Låt Z vara mängden av alla heltal, J alla jämna tal och U alla udda tal. Då är {J, U} en partition av Z.
• Låt Z⁺ vara alla positiva tal och Z^- alla negativa tal. Då är {{0}, Z⁺, Z^-} en partition av Z.

Antal partitioner

Belltalen, ${\displaystyle B_{n}}$ är antalet möjliga partitioner av en mängd med ${\displaystyle n}$ element. Likaså är Stirlingtalen av andra slaget, ${\displaystyle S(n,k)}$ antalet möjliga partitioner av en mängd med ${\displaystyle n}$ element i ${\displaystyle k}$ olika delar.