matematikk.net

Det finnes ganske mange identiteter med binomialkoeffisienter. De fleste av disse kan bevises med enkel algebraisk manipulasjon, men dette gir kanskje ikke allverdens innsikt. Derfor er oppgava å forklare disse identitetene med kombinatoriske argumenter:

[tex](1)\,\,\, {n\choose k} = {n\choose n-k} \\ (2) \,\,\, {n\choose k} = {n-1 \choose k-1}+{n-1\choose k} \\ (3)\,\,\, \sum_{k=0}^n{n\choose k} = 2^n \\ (4)\,\,\, \sum_{k=0}^n(-1)^k{n\choose k} = 0 \\ (5)\,\,\, \sum_{k=0}^n{x\choose k}{y\choose n-k} = {x+y\choose n}\,\,\, (x,y\ge n) \\ (6)\,\,\, \sum_{k=0}^r {n+k\choose k} = {n+r+1\choose r} \\ (7)\,\,\, \sum_{k=0}^n {n\choose k}^2={2n\choose n}[/tex]

Ingen skal nektes å regne på det også, men jeg syns som sagt et kombinatorisk argument er klart å foretrekke.

(4),

[tex]n \choose k[/tex] er symmetrisk om n/2, når k går fra 0 til n, fordi

[tex]{n \choose k} = \frac{n!}{k!(n-k)!}[/tex].

Altså får hvert ledd et tilsvarende negativt ledd "på andre siden av n/2", og summen blir null.

Vet ikke om det holder da.

Det vil fungere fint når n er odde: 1-5+10-10+5-1 er som du beskriver opplagt 0, men hva med 1-4+6-4+1, her har vi ikke samme symmetri.

Nummer 1.
La oss si du har n objekter, du skal se hvor mange måter k objekter kan uordnet fordeles. Dette er [tex]{n \choose k}[/tex]. For hver unike type ordning, må de resterende n-k objektene ha en unik type ordning. Derfor må [tex]{n \choose k} = {n \choose {n-k}}[/tex]

Kommentar til oppg 4:

Vi har at [tex](a+b)^n= \sum_{k=0}^n\ a^{n-k}b^k{n\choose k}[/tex]
Vi setter [tex]a=1 , b=-1[/tex]

Dette gir det ønskede resultatet

regner litt på (2) med traktormetoden...

[tex]{n \choose n-k}={n-1\choose k-1}\,+\,{n-1\choose k}[/tex]

[tex]\frac{n!}{(n-k)!k!}=\frac{(n-1)!}{(k-1)!(n-k)!}\,+\,\frac{(n-1)!}{k!(n-1-k)!}[/tex]

har brukt at: n! = n(n-1)!
og

[tex]\frac{(n-k)!}{(n-1-k)!}=n-k[/tex]

[tex]\frac{n}{k!}=\frac{1}{(k-1)!}\,+\,\frac{(n-k)}{k!}[/tex]

[tex]\frac{n}{k!}=\frac{k}{k(k-1)!}\,+\,\frac{n-k}{k(k-1)!}=\frac{n}{k(k-1)!}=\frac{n}{k!}[/tex]

og VS = HS

Kombinatoriske argument altså... skal vi se:

1) [tex]{n \choose k}[/tex] er jo antall måter å velge ut k elementer fra en populasjon med n elementer. Bytter vi om på betegnelsene "utvalgt" og "ikke utvalgt" burde det være åpenbart at [tex]{n \choose k} = {n \choose {n-k}}[/tex]

2)[tex]{n \choose k}[/tex] er fortsatt alle måter å velge ut k elementer fra en populasjon med n elementer. Lar vi ett element i mengden være gitt, kan vi jo dele disse måtene i de som tar med det gitte elementet, altså [tex] {{n-1} \choose {k-1}}[/tex] stykker, og de som ikke tar med det gitte elementet, [tex]{{n-1} \choose k}[/tex]

totalt [tex]{n \choose k} = {{n-1} \choose {k-1}} + {{n-1} \choose k}[/tex]

3) Totalt antall mulige utvalg vi kan gjøre fra en gitt populasjon med n elementer, A kan vi skrive på to måter:
a) summere opp hvor mange måter vi kan velge k elementer fra n elementer, k går fra 0 til n.
[tex]A=\displaystyle \sum_{k=0}^{n} {n \choose k}[/tex]

b) For hvert element har vi valget om vi skal ta det med i utvalget eller ikke, altså totalt

[tex]A = 2^n[/tex]
mulige utvalg.

4) Hvis vi igjen ser på alle mulige utvalg av en populasjon på n elementer, og lar ett element være gitt, kan vi ordne de mulige utvalgene inn i par slik at den eneste forskjellen mellom de to utvalgene i et par er at det gitte elementet er med i det ene, men ikke i andre. Det er nå åpenbart at vi i hvert par har ett utvalg hvor et odde antall elementer er valgt, og ett utvalg hvor et like antall elementer er valgt. Dermed må antall utvalg med et odde antall elementer og antall utvalg med et like antall elementer være like, og vi har:

[tex]\displaystyle \sum {n \choose {2k}} = \sum {n \choose {2k+1}}[/tex]
[tex]\displaystyle \Rightarrow \sum {n \choose {2k}} - \sum {n \choose {2k+1}} = \sum_{k=0}^n (-1)^k {n \choose k} =0[/tex]


Skal kanskje se på resten i morgen.

Og en liten oppfølgernøtt:

Bevis [tex]\displaystyle \sum_{i=1}^n i = \frac{n (n+1)}{2}[/tex] ved hjelp av kombinatorikk.

Man kan dele [tex]n+1[/tex] elementere inn i [tex]{n+1}\choose2[/tex], men man kan også telle det på denne måten: element nr.1 kan parres med [tex]n[/tex] andre elementer, element nr.2 kan parres med [tex]n-1[/tex] andre elementer (ettersom man ikke teller det parret "1-2" som allerede er tellt), element nr.3 kan parres med [tex]n-2[/tex] andre elementer, osv.
Vi har da tellt opp antallet slike par på to forskjellige måter (antallet blir det samme i begge måtene)
Vi får:
[tex]n+(n-1)+(n-2)+...+1=\sum_{i=1}^n i={{n+1}\choose2}=\frac{n(n+1)}{2}[/tex]

De første ordene skulle være:
Om man har n+1 elementer finnes det [tex]{n+1}\choose2[/tex] måter å lage 2-er-grupper på.