Stirlingtall av andre type (kombinatorikk)
Lagt inn: 13/10-2007 18:11
Vi kjenner alle til binomialkoeffisientene, som forteller oss hvor mange måter man kan plukke ut grupper på k mennesker fra en klasse på n.
Vi skal nå definere en ny, nyttig, kombinatorikkfunksjon - Stirlingtall av andre type. (Ja, det eksisterer også Stirlingtall av første type. Disse kan vi ta for oss en annen gang.)
La [tex]\left{ \begin{array}{c} n \\ k \end{array} \right}[/tex] være antall måter man kan dele en mengde på n elementer inn i k ikke-tomme undermengder. (En slik oppdeling kalles en partisjonering.) [tex]\left{ \begin{array}{c} n \\ k \end{array} \right}[/tex] kalles et Stirlingtall av andre type.
En annen måte å si det på, er at det er antall måter å putte n ulike baller i k ulike kopper.
For eksempel er [tex]\left{ \begin{array}{c} 4 \\ 3 \end{array} \right} = 6[/tex], siden det finnes 6 måter man kan partisjonere en mengde på 4 elementer i 3 mengder. Disse partisjonene viser vi her på mengden {a, b, c, d}:
{a}, {b}, {c, d}
{a}, {c}, {b, d}
{a}, {d}, {b, c}
{b}, {c}, {a, d}
{b}, {d}, {a, c}
{c}, {d}, {a, b}
Nå som vi vet hva et Stirlingtall er, la oss prøve oss på noen oppgaver:
Vis at:
a) [tex]\left{ \begin{array}{c} n \\ 1 \end{array} \right} = 1[/tex]
b) [tex]\left{ \begin{array}{c} n \\ 2 \end{array} \right} = 2^{n-1}-1[/tex]
c) [tex]\left{ \begin{array}{c} n \\ n-1 \end{array} \right} = {n \choose 2}[/tex]
d) Tenk deg at du skal gi n barn ispinner, en ispinne per barn. Disse ispinnene har k ulike smaker. Vis at antall måter vi kan dele ut ispinner på, når vi deler ut minst en pinne av hver smak, er [tex]k! \left{ \begin{array}{c} n \\ k \end{array} \right}[/tex]
e) Finn en formel for hvor mange is som må deles ut dersom bare m av de n smakene må deles ut. ([tex]0 \leq m \leq n[/tex])
f) Vis at [tex]\left{ \begin{array}{c} n \\ k \end{array} \right} = \frac{1}{k!} \sum _{r=0} ^k (-1)^r {k \choose r}(k-r)^n[/tex]
g) Stirlingtallene har en interessant "parallell" til binomialteoremet: Vi definerer
[tex]x^{\underline{r}} = x(x-1)(x-2)...(x-r+1)[/tex]
(Slik er [tex]x^{\underline{r}}[/tex] produktet av r faktorer)
Bevis at:
[tex]x^n = \left{ \begin{array}{c} n \\ 1 \end{array} \right}x^{\underline{1}} + \left{ \begin{array}{c} n \\ 2 \end{array} \right}x^{\underline{2}} + ... + \left{\begin{array}{c} n \\ n \end{array} \right}x^{\underline{n}}[/tex]
Oppgavene er hentet fra Paul Zeitz' fantastiske bok "The Art and Craft of Problem Solving"
Vi skal nå definere en ny, nyttig, kombinatorikkfunksjon - Stirlingtall av andre type. (Ja, det eksisterer også Stirlingtall av første type. Disse kan vi ta for oss en annen gang.)
La [tex]\left{ \begin{array}{c} n \\ k \end{array} \right}[/tex] være antall måter man kan dele en mengde på n elementer inn i k ikke-tomme undermengder. (En slik oppdeling kalles en partisjonering.) [tex]\left{ \begin{array}{c} n \\ k \end{array} \right}[/tex] kalles et Stirlingtall av andre type.
En annen måte å si det på, er at det er antall måter å putte n ulike baller i k ulike kopper.
For eksempel er [tex]\left{ \begin{array}{c} 4 \\ 3 \end{array} \right} = 6[/tex], siden det finnes 6 måter man kan partisjonere en mengde på 4 elementer i 3 mengder. Disse partisjonene viser vi her på mengden {a, b, c, d}:
{a}, {b}, {c, d}
{a}, {c}, {b, d}
{a}, {d}, {b, c}
{b}, {c}, {a, d}
{b}, {d}, {a, c}
{c}, {d}, {a, b}
Nå som vi vet hva et Stirlingtall er, la oss prøve oss på noen oppgaver:
Vis at:
a) [tex]\left{ \begin{array}{c} n \\ 1 \end{array} \right} = 1[/tex]
b) [tex]\left{ \begin{array}{c} n \\ 2 \end{array} \right} = 2^{n-1}-1[/tex]
c) [tex]\left{ \begin{array}{c} n \\ n-1 \end{array} \right} = {n \choose 2}[/tex]
d) Tenk deg at du skal gi n barn ispinner, en ispinne per barn. Disse ispinnene har k ulike smaker. Vis at antall måter vi kan dele ut ispinner på, når vi deler ut minst en pinne av hver smak, er [tex]k! \left{ \begin{array}{c} n \\ k \end{array} \right}[/tex]
e) Finn en formel for hvor mange is som må deles ut dersom bare m av de n smakene må deles ut. ([tex]0 \leq m \leq n[/tex])
f) Vis at [tex]\left{ \begin{array}{c} n \\ k \end{array} \right} = \frac{1}{k!} \sum _{r=0} ^k (-1)^r {k \choose r}(k-r)^n[/tex]
g) Stirlingtallene har en interessant "parallell" til binomialteoremet: Vi definerer
[tex]x^{\underline{r}} = x(x-1)(x-2)...(x-r+1)[/tex]
(Slik er [tex]x^{\underline{r}}[/tex] produktet av r faktorer)
Bevis at:
[tex]x^n = \left{ \begin{array}{c} n \\ 1 \end{array} \right}x^{\underline{1}} + \left{ \begin{array}{c} n \\ 2 \end{array} \right}x^{\underline{2}} + ... + \left{\begin{array}{c} n \\ n \end{array} \right}x^{\underline{n}}[/tex]
Oppgavene er hentet fra Paul Zeitz' fantastiske bok "The Art and Craft of Problem Solving"