Partition av en mängd

Partitionering av en mängd (cirkeln) i sju delar (de färgade områdena).

För andra betydelser, se partition.

En partition 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 $M$ är en mängd som består av icke-tomma delmängder till $M$ sådan att varje element i $M$ tillhör en och endast en av dessa delmängder.

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

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

Detta kan skrivas symboliskt:

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

Notera alltså att elementen i $P$ inte kallas partitioner, utan $P$ kallas partition.

Exempel

• En mängd innehållande ett element, $\{x\}$ kan partitioneras på ett sätt: $\{\{x\}\}$.
• En partitionering av $\{1,2,3\}$ är $\{\{1\},\{2,3\}\}$, en annan är $\{\{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, $B_{n}$ är antalet möjliga partitioner av en mängd med $n$ element. Likaså är Stirlingtalen av andra slaget, $S(n,k)$ antalet möjliga partitioner av en mängd med $n$ element i $k$ olika delar.