Stirlingtal

Från Rilpedia

Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif

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

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:

s(n,k) = \left[{n \atop k}\right]
S(n,k) = \left\{\begin{matrix} n \\ k \end{matrix}\right\}

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, \left[{n \atop k}\right], ä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]):

[1, 2, 3] ~~ [1, 3, 2]

Så att \left[{3 \atop 1}\right] = 2. 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 \left[{0 \atop 0}\right] = 1, det finns ett sätt att placera inga element i noll icketomma cykler, i övrigt gäller att \left[{n \atop 0}\right] = 0 (n \neq 0), 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 \left[{n \atop n}\right] = 1 , 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:

\left[{n \atop k}\right] = (n-1)\left[{n-1 \atop k}\right]+\left[{n-1 \atop k-1}\right]

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,  \left\{\begin{matrix} n \\ k \end{matrix}\right\} , 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  \left\{\begin{matrix} 4 \\ 2 \end{matrix}\right\} , ser vi att vi kan göra det på sju sätt:

\{1, 2, 3\} \cup \{4\} ~~ \{1, 2, 4\} \cup \{3\} ~~ \{1, 3, 4\} \cup \{2\} ~~ \{2, 3, 4\} \cup \{1\} ~~ \{1, 2\} \cup \{3, 4\} ~~ \{1, 3\} \cup \{2,4\} ~~ \{1, 4\} \cup \{2, 3\}

D v s,  \left\{\begin{matrix} 4 \\ 2 \end{matrix}\right\} = 7.

Stirlingtal av andra slaget på formen  \left\{\begin{matrix} n \\ 1 \end{matrix}\right\} = 1 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  \left\{\begin{matrix} 0 \\ 0 \end{matrix}\right\} = 1, men en icketom mängd kan inte delas upp i noll mängder på något sätt, så att  \left\{\begin{matrix} n \\ 0 \end{matrix}\right\} = 0 . 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 \left\{\begin{matrix} n \\ n \end{matrix}\right\} = 1.

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

 \left\{\begin{matrix} n \\ k \end{matrix}\right\} = k\left\{\begin{matrix} n - 1 \\ k \end{matrix}\right\} + \left\{\begin{matrix} n - 1 \\ k - 1 \end{matrix}\right\}

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:

\left[{n \atop k}\right] \geq \left\{\begin{matrix} n \\ k \end{matrix}\right\}

Det är ganska lätt att inse att:

\left[{n \atop n}\right] = \left\{\begin{matrix} n \\ n \end{matrix}\right\}

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:

\left[{n \atop n-1}\right] = \left\{\begin{matrix} n \\ n-1 \end{matrix}\right\} = \begin{pmatrix} n \\ 2 \end{pmatrix}

Personliga verktyg