Stirlingtal

Från Wikipedia
Hoppa till: navigering, sök

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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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:

n\k 0 1 2 3 4 5
0 1
1 0 1
2 0 1 1
3 0 2 3 1
4 0 6 11 6 1
5 0 24 50 35 10 1


Stirlingtal av andra slaget[redigera | redigera wikitext]

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:

n\k 0 1 2 3 4 5
0 1
1 0 1
2 0 1 1
3 0 1 3 1
4 0 1 7 6 1
5 0 1 15 25 10 1

Relationer med Stirlingtal[redigera | redigera wikitext]

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