Surjectieve afbeeldingen en partities
[volgende][vorige][inhoud] (versie: 23 augustus 2011)
9.6Surjectieve
afbeeldingen en partities
9.6.1Surjectieve afbeeldingen
We leiden een formule af voor het aantal surjectieve afbeeldingen van
naar
.
Laat de verzameling zijn
van alle afbeeldingen van
naar .
We gebruiken het principe van inclusie-exclusie. Als indexverzameling nemen we
. Laat
voor de
deelverzameling
van bestaan
uit alle
met . Voor
hebben we
dan en dus
. Afbeeldingen met
elementen in het beeld
zijn afbeeldingen met
elementen buiten het beeld. Dus het aantal is
We hebben dus afgeleid:
9.41 Propositie.Het aantal surjectieve afbeeldingen van een verzameling metelementen naar een verzameling metelementen is gelijk aan
9.42Voorbeeld. Op een bingo-avond kunnen
prijzen worden gewonnen door
mensen. Wat is de kans dat iedereen
een prijs wint? De kans is het quotiënt van het aantal surjectieve afbeeldingen van
naar
en het totale aantal afbeeldingen. Het aantal surjecties is:
en het totale aantal afbeeldingen is .
Zie ook Voorbeeld 9.50.
9.6.2Partities met
klassen
9.43 Definitie. Laten
natuurlijke getallen zijn. We definiëren het Stirlinggetal
van de tweede soort als het aantal partities
van een verzameling met
elementen, waarbij .
9.44Voorbeeld. De partities van
die uit twee klassen bestaan zijn:
Dus .
De Schotse wiskundige James Stirling (Garden 1692 – Edinburgh 1770) was een
tijdgenoot van Euler. Hij werkte in de traditie van Newton op het gebied van de
calculus. Hij is vooral bekend door de formule van Stirling
een benadering van
die waarschijnlijk al eerder gevonden is door de Franse wiskundige Abraham deMoivre (Vitry-le-François 1667 – Londen 1754) die, nadat hij Frankrijk was
ontvlucht, vooral in Engeland heeft gewerkt.
De Stirlinggetallen kunnen, net zoals de binomiaalcoëfficiënten, in een
driehoek worden geplaatst. Daarbij kan de volgende recursieve beschrijving worden
gebruikt.
9.45 Stelling.Stirlinggetallen van de tweede soort voldoen aan:
voor alle ,
voor alle ,
voor alle met .
Bewijs. De eerste twee onderdelen zijn eenvoudig. Kies voor het laatste onderdeel een vast element
in een
verzameling met
elementen. Er zijn twee
soorten partities in
klassen:
partities
met ;
hiervan zijn er ,
partities
met ;
deze ontstaan uit een partitie met
klassen van
door het element
aan een van deze
klassen toe te voegen; daarvan zijn er dus .
□
Voor kleine
krijgen we de aantallen als in Figuur 9.10.
Figuur 9.10:
Driehoek van Stirlinggetallen van de tweede soort
Algoritme
Voor het berekenen van de Stirlinggetallen van de tweede soort geldt hetzelfde als
voor de berekening van de binomiaalcoëfficiënten.
Python
De Pythoncode is analoog aan die voor de berekening van de binomiaalcoëfficiënten.
def stirling2(n,k): list0 = [1] + (n - k) * [0] i = j = 0 while i<k: list1 = [1] i = i + 1 while j<n-k: j = j + 1 list1.append(i * list1[-1] + list0[j]) list0 = list1 j = 0 return list0[-1]
In het schema van de Stirlinggetallen van de tweede soort staan in de
-de rij de aantallen
partities van
bij gegeven aantallen klassen.
9.46 Definitie. Het -de
Bellgetal
is het aantal partities van een verzameling van
elementen.
We hebben dus:
9.47 Propositie.Voor iedere geldt .□
9.48Voorbeeld. Het Bellgetal is te berekenen uit de Stirlinggetallen van de tweede soort, zie
Figuur 9.10:
Eric Temple Bell (Peterhead, Schotland 1883 – Watsonville, USA 1960)
De Bellgetallen zijn genoemd naar Eric Temple Bell. Hij is bekend als schrijver van boeken
over de geschiedenis van de wiskunde. Onder de naam John Taine schreef hij science
fiction.
Een surjectieve afbeelding van
naar bepaalt
een partitie van
in klassen.
Zo’n partitie
hoort bij
van zulke surjectieve afbeeldingen: deze corresponderen met bijecties
. Uit
Propositie 9.41 volgt dus:
9.49 Propositie.Voorgeldt
9.50Voorbeeld. We komen terug op Voorbeeld 9.42. Het aantal surjecties van
naar
is
en dit
is met behulp van de recursieve beschrijving van de Stirlinggetallen sneller te berekenen dan de
in 9.42 gevonden som.