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.

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

Formell definition redigera

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

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

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

Detta kan skrivas symboliskt:

  •  
  •  .

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

Exempel redigera

  • En mängd innehållande ett element,   kan partitioneras på ett sätt:  .
  • En partitionering av   är  , en annan är  .
  • 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

Belltalen,   är antalet möjliga partitioner av en mängd med   element. Likaså är Stirlingtalen av andra slaget,   antalet möjliga partitioner av en mängd med   element i   olika delar.