Partition av en mängd

Från Wikipedia
Hoppa till: navigering, sök
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[redigera | redigera wikitext]

En partition av en mängd  M är en mängd som består av icke-tomma delmängder till  M sådan att ett element i  M finns i exakt 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[redigera | redigera wikitext]

  • 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[redigera | redigera wikitext]

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.