subsetsamenstellingen

Subsetsamenstelling is in de combinatoriek de verdeling van een verzameling in niet-lege, wederzijds disjunkte deelverzamelingen die samen de oorspronkelijke verzameling vormen. Deze deelverzamelingen worden vaak blokken of delen genoemd. Een dergelijke verdeling wordt ook wel een partition van de verzameling genoemd.

Belangrijke onderscheidingen zijn onder meer of de volgorde van de blokken meespeelt. Bij een ongesorteerde verdeling (een standaardsetpartitie) telt men twee verdelingen als gelijk als ze dezelfde blokken bevatten, ongeacht de volgorde van de blokken. Bij geordende verdeels (ordered partitions) telt de volgorde van de blokken wel mee, wat leidt tot andere telgetallen.

Veel voorkomende aantallen rondom subsetcomposities zijn onder meer:

- Het aantal partitioneringen van een verzameling met n elementen in exactly k niet-lege blokken: de Stirling-getallen van de tweede soort S(n,k).

- Het totale aantal partities van een n-elementenverzameling: de Bell-getallen B_n.

- Voor geordende verdeels bestaan er toenames zoals de zogenaamde ordered Bell-getallen of Fubini-getallen.

Voorbeelden: voor S = {1,2,3} zijn er vijf partities: {{1},{2},{3}}, {{1,2},{3}}, {{1,3},{2}}, {{2,3},{1}}, {{1,2,3}}. Als men de volgorde van de blokken toelaat, komen er extra varianten bij.

Toepassingen van subsetsamenstellingen komen voor in clustering, data-structuren, probability en combinatorische modellering, waar men vaak interesse heeft in hoe een verzameling kan worden opgesplitst in niet-overlappende groepen.

In wiskundige notaties wordt een subsetcompositie vaak gezien als een partition of een set, met combinatorische tellingen gericht op het aantal mogelijke verdeelscenario’s voor een gegeven verzameling.