Från Rilpedia

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

Innehåll 1 Notation 2 Stirlingtal av första slaget 3 Stirlingtal av andra slaget 4 Relationer med Stirlingtal

Notation

Stirlingtal av första slaget betecknas ibland s(n,k) och Stirlingtal av andra slaget betecknas ibland S(n,k). 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 n element i k icketomma cykler, d v s ordningar av tal som är cykliska permutationer av varandra. Om vi har mängden A = {1,2,3} kan vi från den konstruera 2 olika cykler med 3 element i varje (vi betecknar en cykel med [1,2,...,n]):

Så att . Observera alltså att [1,2,3] = [2,3,1] = [3,1,2], 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 icketomma cykler, i övrigt gäller att (), för det finns inget sätt att placera ut n element i noll icketomma cykler. För Stirlingtal av första slaget ser man att , för det finns ett sätt att placera ut n element i n icketomma 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

Stirlingtal av andra slaget, , ger antal sätt att dela in en mängd med n element i k icketomma mängder.

Om vi t ex har en mängd med fyra element, exempelvis A = 1,2,3,4 och vill veta på hur många sätt vi kan dela upp A 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 n, eftersom en mängd bara kan delas upp i en mängd med lika många element på ett sätt. Om k = 0 kan vi säga att det bara finns ett sätt att dela in en tom mängd i noll icketomma mängder, så att , men en icketom 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 n element i n 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

Man kan se att antal 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 n element i n − 1 cykler eller delmängder får man exakt en cykel eller delmängd som innehåller två element, och då [a,b] = [b,a] så är detta samma sak som att välja ut de två element som kommer hamna i samma delmängd eller cykel, så att: