Stirlinggetallen

Stirlinggetallen zijn verzamelnaam voor twee families van getallen in de combinatoriek, genoemd naar James Stirling. Ze helpen bij het uitdrukken van machten in termen van getallen met een afgeleide structuur en hebben verschillende combinatoriële interpretaties. In de literatuur worden meestal onderscheiden: Stirlinggetallen van de tweede soort, S(n, k) (ook geschreven als {n \brace k}), en Stirlinggetallen van de eerste soort, vaak aangeduid met s(n, k) voor de getekende variant en met c(n, k) voor het unsigned geval.

Stirlinggetallen van de tweede soort S(n, k) tellen het aantal manieren om een verzameling met n elementen op te splitsen in k niet-lege, ongelabelde subsetten. Ze voldoen aan de recursie S(n, k) = S(n-1, k-1) + k S(n-1, k) met S(0,0)=1 en S(n,0)=0 voor n>0; ook geldt S(n,n)=1. Deze getallen vormen een driehoek, vergelijkbaar met binomiale coëfficiënten, en komen voor in uitdrukkingen zoals elke macht x^n uitgedrukt kan worden als een lineaire combinatie van valkórsproductvormen.

Stirlinggetallen van de eerste soort tellen het aantal permutaties van n elementen die precies k cycli bevatten. Voor de unsigned variant wordt dit getal aangeduid als c(n,k) en zij voldoen aan c(n,k) = c(n-1,k-1) + (n-1) c(n-1,k) met c(0,0)=1. De signed variant s(n,k) voldoet aan s(n,k) = s(n-1,k-1) − (n-1) s(n-1,k) en verschijnt met een teken (-1)^{n-k}. Verhouding met factorials en polynoomuitdrukkingen geeft: x^n = sum_{k=0}^n S(n,k) x^{\underline{k}} en x^{\underline{n}} = sum_{k=0}^n s(n,k) x^{k}, waarbij x^{\underline{k}} de dalende factorial is.

Toepassingen omvatten het uitdrukken van machten in termen van dalende factorialen, Faulhabers formules, en diverse tellingen in combinatoriek en kansrekening.