WisFaq!

Aantal partities

Dag,

'k heb twee vragen:

Hoe kan ik uitrekenen in hoeveel verschillende partities een (eindige) verzameling verdeeld kan worden?

Bij reflexiviteit moet dan gelden dat voor elementen die tot verzameling V behoren er een koppel bestaat? Dus van verzameling {a,b,c} is de relatie {(a,a),(b,b)} niet reflexief omdat (c,c) er niet in zit?

Groet

Thijs
6-1-2007

Antwoord

Dag Thijs,

Wat je vraag over reflexiviteit betreft: dat klopt.
Dan over het aantal partities: het is niet zo eenvoudig om daar een algemene formule voor op te stellen. Als je dit aantal wil bepalen voor een bepaald gegeven getal, zou ik eerst proberen het aantal partities te berekenen zonder te kijken naar de elementen, bijvoorbeeld een verzameling van vier elementen kan je verdelen in 4, 3+1, 2+2, 2+1+1, 1+1+1+1. En dan moet je geval per geval nagaan hoeveel partities er bij elk van deze verdelingen horen.

Het aantal dat je zoekt, is gekend onder de naam 'Bell number'. Op deze link kan je er alles over vinden: de definitie, een recursieve formule, enkele toch vrij verrassende berekeningsmethoden (formules 4 tot 8), asymptotisch gedrag (wat gebeurt er als het aantal elementen in je eindige verzameling groot wordt, formule 10), enzovoort.

Groeten,
Christophe.

Christophe
8-1-2007