Stirlingtal

Stirlingtal används inom matematiken för att beskriva antalet permutationer eller partitioner av storlek  av en mängd av storlek .  Det finns två slags Stirlingtal, Stirlingtal av första slaget och Stirlingtal av andra slaget. Stirlingtalen är uppkallade efter matematikern James Stirling.

Notation
Stirlingtal av första slaget betecknas ibland  och Stirlingtal av andra slaget betecknas ibland . En annan notation är:

Denna notation med hak- och klammerparenteser, som är analog med notationen för binomialkoefficienter, infördes av Jovan Karamata.

Stirlingtal av första slaget
Stirlingtal av första slaget, , är antalet sätt att ordna  element i  icke-tomma cykler, d.v.s. ordningar av tal som är cykliska permutationer av varandra. Om vi har mängden  kan vi från den konstruera 2 olika cykler med 3 element i varje (vi betecknar en cykel med ):

Så att . Observera alltså att , vi kan plocka en siffra framifrån och sätta längst bak.

Man ser att , det finns ett sätt att placera inga element i noll icke-tomma cykler, i övrigt gäller att  (), för det finns inget sätt att placera ut  element i noll icke-tomma cykler. För Stirlingtal av första slaget ser man att , för det finns ett sätt att placera ut  element i  icke-tomma cykler (varje cykel innehåller då ett element).

Man kan räkna ut Stirlingtal av första slaget med följande rekursiva ekvation:

Några exempel på Stirlingtal av första slaget:

Stirlingtal av andra slaget
Stirlingtal av andra slaget, , ger antal sätt att dela in en mängd med  element i  icke-tomma mängder.

Alternativt kan Stirlingtalet S(n,k) definieras som antalet oordnade surjektioner av en mängd av n element på en mängd av k element. Om det totala antalet surjektioner är N, så är S(n,k) = N/k!.
S(n,k) kan även beskrivas som antalet möjligheter att placera n numrerade bollar i k identiska (onumrerade) lådor, med restriktionen minst en boll i varje låda.

Om vi t.ex. har en mängd med fyra element, exempelvis  och vill veta på hur många sätt vi kan dela upp  i två mängder, d.v.s. räkna ut , ser vi att vi kan göra det på sju sätt:

d.v.s., . 

Stirlingtal av andra slaget på formen  för positiva , eftersom en mängd bara kan delas upp i en mängd med lika många element på ett sätt. Om  kan vi säga att det bara finns ett sätt att dela in en tom mängd i noll icke-tomma mängder, så att , men en icke-tom mängd kan inte delas upp i noll mängder på något sätt, så att . Man inser också att det går att dela in en mängd med  element i  mängder på ett sätt, så att .

Stirlingtal av andra slaget kan räknas ut rekursivt med:

Några Stirlingtal av andra slaget är:

Relationer med Stirlingtal
Man kan se att antalet möjliga cykler av en mängd är större än eller lika med antalet möjliga mängder, d.v.s.:

Det är ganska lätt att inse att:

Man kan också koppla ihop Stirlingtalen med binomialkoefficienter: När man ska ordna  element i  cykler eller delmängder får man exakt en cykel eller delmängd som innehåller två element, och då  så är detta samma sak som att välja ut de två element som kommer hamna i samma delmängd eller cykel, så att:

Stirlingtalen av första och andra slaget kan ses som varandras inverser:

och

där  är Kroneckerdeltat. Två andra liknande formler är

och

Diskret matematik
Heltalsmängder
Permutationer