Stirlingtall av andre type (kombinatorikk)

[daofeishi]

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"

[euklid]

La [tex]\{\frac{n}{k}\}[/tex] detonere Stirlingtall av andre type. La [tex]X=\{1,..,n\}[/tex]
a) [tex]X[/tex] er en partisjon av seg selv og den er unik.
b) La [tex]X=A\cup B[/tex] hvor [tex]A\cap B=\emptyset[/tex]. For [tex]x\in X[/tex] har vi [tex]2[/tex] alternativer for hver element. Dette gir [tex]2^{n}[/tex] forskjellige muligheter. Vi har krevd at [tex]A,B\neq\emptyset[/tex]. Derfor må mengdene inneholde minst ett element slik at vi kan fjerne tilfellene der enten [tex]A,B=\emptyset[/tex]. Dette gir [tex]2^{n}-2[/tex] forskjellige muligheter. Siden [tex]A,B[/tex] ikke er ordnet (dvs. vi får to partisjoner der [tex]A_1=B_2[/tex] og [tex]A_2=B_1[/tex] for partisjonene [tex]X=A_1\cup B_1=A_2\cup B_2[/tex] ) får vi [tex]2^{n-1}-1[/tex].
c) Vha dueskuffeprinsippet må et av [tex]n-1[/tex] mengdene inneholde akkurat to elementer. Resten av mengdene må inneholde ett element hver pga kriteriet om ikketomme. Vi trenger derfor kun å avgjøre antall mulige måter å plukke ut [tex]2[/tex] elementer av [tex]n[/tex]. Dette gir selvfølgelig [tex]{n \choose 2}[/tex].