Stirlingtal

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

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.

Notation[redigera | redigera wikitext]

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

Stirlingtal av första slaget, \left[{n \atop k}\right], är antalet sätt att ordna  n element i  k icke-tomma 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 icke-tomma 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 icke-tomma 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 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:

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

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 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  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 icke-tomma mängder, så att  \left\{\begin{matrix} 0 \\ 0 \end{matrix}\right\} = 1, men en icke-tom 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[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.:

\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}