Bellgetallen

Bellgetallen zijn een rij natuurlijke getallen die in de combinatoriek voorkomen. Voor elk niet-negatief geheel n tellen ze het aantal manieren om een verzameling met n elementen te verdelen in niet-lege blokken, waarbij de volgorde van de blokken geen rol speelt. Met andere woorden zijn het de partitities van een n-elementenverzameling, en daarmee ook het aantal equivalente relaties op zo’n verzameling.

De bellgetallen zijn nauw verbonden met de Stirling getallen van de tweede soort S(n,k). In formule-vorm geldt: B(n) = sum_{k=0}^n S(n,k). Daarmee telt B(n) het totale aantal manieren om een set met n elementen op te splitsen in k blokken, over alle mogelijke k. Een veelgebruikte recursie is B(0) = 1 en voor n ≥ 0: B(n+1) = sum_{k=0}^n binom(n,k) B(k). De exponentiële generating function luidt: sum_{n≥0} B(n) x^n / n! = exp(exp(x) - 1). Een andere beschrijving is Dobinski’s formule: B(n) = (1/e) sum_{k≥0} k^n / k!.

Enkele beginwaarden zijn: B(0) = 1, B(1) = 1, B(2) = 2, B(3) = 5, B(4) = 15, B(5) = 52, B(6) = 203. Bellgetallen groeien snel en illustreren de explosieve aard van partities van verzamelingen. De naam is ontleend aan Eric Temple Bell, die ze in de twintigste eeuw introduceerde.

Zie ook: Stirlinggetallen van de tweede soort; partitities; Bell-triangle.