10.13 Definitie. Laten
natuurlijke getallen zijn. We definiëren het Stirlinggetal
van de eerste soort als het aantal permutaties
van een verzameling
met
elementen, waarbij .
(Met
geven we de verzameling van banen van
aan.)
10.14Voorbeeld. De permutaties van
met
banen zijn:
Dus .
Uit de volgende stelling volgt dat ook deze Stirlinggetallen op recursieve wijze berekend
kunnen worden.
10.15 Stelling.Stirlinggetallen van de eerste 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 permutaties van
met
banen:
permutaties
met ;
hiervan zijn er ;
permutaties
met ;
deze ontstaan uit een permutatie met
banen van
door het element
aan een van deze
banen toe te voegen (dat kan op
manieren); in totaal zijn er dus
van deze permutaties. □
Voor kleine
krijgen we de getallen in Figuur 10.2.
Figuur 10.2:
Driehoek van Stirlinggetallen van de eerste soort
Berekening van Stirlinggetallen van de eerste soort
Het berekenen van deze Stirlinggetallen gaat op dezelfde manier als voor die van
de tweede soort en voor binomiaalcoëfficiënten.
Python
Een kleine aanpassing van de code voor de Stirlinggetallen van de tweede soort voldoet.
We zetten de code in de module combinatorics.py.
def stirling1(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 + j - 1) * list1[-1] + list0[j]) list0=list1 j = 0 return list0[-1]