Kombinatoriske tolkninger av identiteter

[Karl_Erik]

I denne tråden har jeg lyst til å samle sammen morsomme kombinatorikkidentiteter som har en forholdsvis fornuftig kombinatorisk tolkning. Det er bare å bidra om en har noen spennende oppgaver, under den forutsetning at en selv har en løsning av den ved en kombinatorisk tolkning. Løsninger gjennom algebraisk manipulasjon eller andre teknikker er altså 'ikke lov' i denne tråden. Akkurat hva en kombinatorisk tolkning er vil jeg la være litt løst definert, men om løsningen din dreier seg mer om telling enn om likninger er det en veldig god start.

Under er det spesielt i starten en del forholdsvis velkjente oppgaver - har en sett dem før kan en selvfølgelig skrive inn en løsning om en vil, men det er kanskje morsommere om en overlater dem til folk som ikke har sett dem før.

a) [tex]\sum_{i=0}^n { {n} \choose {i} } = 2^n[/tex]
b) [tex]{ n \choose m } {m \choose k} = {n \choose k} {n-k \choose m-k}[/tex]
c) [tex]\sum_{i=0}^n { {n} \choose {i} }^2 = { {2n} \choose {n} }[/tex]
d)[tex]{ n+m \choose k } = \sum_{i=0}^k { m \choose i } {n \choose k-i}[/tex]
e) [tex]\sum_{i=k}^n {i \choose k} = { n+1 \choose k+1}[/tex]
f) [tex]\sum_{i=0}^{\lfloor \frac n 2 \rfloor} { {n} \choose {2i} } = 2^{n-1}[/tex]
g) [tex](n+1) {n \choose k} = (k+1) { n+1 \choose k+1 }[/tex]
h) [tex]\sum_{i=0}^n {n \choose i} {n-i \choose m-i} = 2^m {n \choose m}[/tex]

[Charlatan]

Følgende scenario har en interessant kombinatorisk tolkning:

La oss si du har n stener i en haug. Du deler opp haugen i to, og multipliserer antall stener i hver haug og skriver ned tallet du får på ei tavle.

Du gjør deretter det samme med de to resterende haugene: deler dem opp i to og multipliserer antall stener i hver haug og skriver begge tallene opp på tavla.

Du fortsetter å gjøre dette, deler opp hver haug i to, multipliserer og skriver opp tallet på tavla til du ender opp med hauger av èn sten i hver haug.

Nå summerer du alle tallene du har skrevet opp på tavla.

Vis at summen du ender opp med er det samme uansett hvordan du deler opp haugene, og finn dette tallet.

Et eksempel: la oss si du har 10 stener i en haug. Du deler opp med 3 stener i en haug, og 7 stener i den andre. Du skriver opp 3*7 = 21 på tavla. Deretter deler du opp haugen med 3 stener i 1 og 2 stener, multipliserer: 2*1 = 2 og skriver tallet opp på tavla. Du tar den andre haugen på 7 og deler opp med 3 og 4 stener i hver haug og skriver opp 4*3 = 12 på tavla. Og slik fortsetter du til du får hauger med èn sten i hver.

[Charlatan]

d) La oss si du har to kasser med forskjellige baller. Den første kassen inneholder n baller, og den andre m baller. Du skal finne ut hvor mange måter du kan velge k baller til sammen. Det er selvsagt [tex]{n+m \choose k}[/tex] måter. Men dette kan også utregnes på følgende måte:

Vi ser på hvert av tilfellene hvor du velger i baller fra den første kassen, og k-i baller fra den andre. For forskjellige i vil vi har forskjellige utplukk, og ethvert utvalg vil også være av denne typen, så vi kan summere opp dette for hver i fra 0 til k for å få det totale antall måter å velge k baller på.

Det er [tex]{ n \choose i}[/tex] måter å velge i baller fra den første kassen (også hvis i>n), og [tex]{ m \choose k-i}[/tex] måter å velge baller fra den andre kassen. Dette gir [tex]{ n \choose i} { m \choose k-i}[/tex] måter å velge k baller med i fra den første og k-i fra den andre. Når vi summerer opp dette får vi identiteten.

[Karl_Erik]

Oppgaven din likte jeg veldig godt. En måte å dele opp haugene på er å ta en og en stein, og da ende med summen [tex]n(n-1) \choose 2[/tex]. Det er heller ikke så vanskelig å bruke fullstendig induksjon til å vise at en faktisk må ende med dette uansett, men den kombinatoriske tolkningen er uansett mer tilfredsstillende.

Vi vil argumentere for at summen en ender opp med er antall måter å velge to av de n ballene på. Dette er sant fordi hver gang vi deler opp haugen i to mindre hauger av størrelser a og b vil ethvert utvalg av baller være en av to - enten tar vi en ball fra hver haug, som kan gjøres på [tex]a \cdot b[/tex] måter, eller så tar vi to baller fra samme haug. Summeringen av tall på slutten svarer altså til en hel rekke forskjellige tilfeller.

Kanskje mer klart er det å si at et utvalg av to bestemte stener i og j vil telles med i det trinnet der sten i og sten j skilles fra å ligge i en haug til å ligge i to separate hauger. (Vi teller da selvfølgelig 'riktig antall' utvalg, siden det som sagt er ab måter å velge en stein fra en haug på a og en stein fra en haug på b på.) Alle utvalg vil da måtte telles med, siden vi ender med en haug for hver sten, og intet utvalg telles to ganger siden vi da måtte ha hatt to steiner som ble skilt fra hverandre to ganger. Altså er summen vi ender opp med antallet måter å velge to steiner fra den opprinnelige haugen på n på, og derfor selvfølgelig uavhengig av valgene vi gjorde underveis.

Løsningen din er forøvrig helt riktig, og identiteten du viste er kjent som Vandermondes identitet.

[Charlatan]

Jeg kom forresten over en geometrisk løsning på den oppgaven samme sted jeg så oppgaven. Selv om den ikke er kombinatorisk er den for interessant til ikke å nevne:

Tegn opp et diagram med n-1 rader på følgende måte:

Code: Select all

x
xx
xxx
xxxx
xxxxx
xxxxxx
xxxxxxx
xxxxxxxx

der k-te rad har k-stener. I dette tilfellet er det 9 stener. Å dele opp de n stenene i to hauger, med den ene av k stener, gir oss noe på formen:

Code: Select all

x
xx
xxx
oooo
oooox
ooooxxx
ooooxxxx
ooooxxxxx

der vi velger en rad k og erstatter alle stenene i rad k med o'er, og alle x'ene direkte under hver o. I dette tilfellet valgte vi rad 4. Høyden vil generelt være n-k, i dette tilfellet 9-4 = 5. Å multiplisere antall stener i hver haug gir oss antall o'er. Dette resulterer i to andre trekanter som korresponderer til henholdsvis 4 og 5 stener. Fortsetter vi får vi og beregner antall o'er til vi har erstattet alle x'ene ender vi opp med det totale antall x'er, som er 1+2+...+n-1 = n(n-1)/2 til sammen. Vi vil beregne det samme antall x'er uansett hvordan vi velger radene våre.

Jeg fant også en fin løsning som tilsvarer din: Man fester en kort strikk mellom hver av de n-stenene. Når man generelt deler opp en haug i to hauger ryker nøyaktig samme antall strikk som produktet av antallet i hver haug. Summen blir altså antall strikk vi hadde til å begynne med. Dette synes jeg gjorde det hele både mer kortfattelig og anskuelig.

[Charlatan]

b)

[tex]{n \choose m} {m \choose k} = {n \choose k} {n-k \choose m-k}[/tex]

Av n mennesker skal vi velge et lag på m, hvorav k er ledere og resten undersåtter.

Vi finner først ut hvor mange slike lag vi kan velge, og multipliserer med antall måter vi kan finne ledere blant disse. Dette gir identiteten til venstre.

Vi finner nå ut hvor mange måter vi kan velge ut våre k ledere. Av de gjenværende n-k finner vi hvor mange måter vi kan velge ut m-k undersåtter, og antall måter å kombinere dette på er produktet. Dette gir identiteten til høyre.


Kom igjen folkens, disse oppgavene er for alle!

[Karl_Erik]

Jeg fant også en fin løsning som tilsvarer din: Man fester en kort strikk mellom hver av de n-stenene. Når man generelt deler opp en haug i to hauger ryker nøyaktig samme antall strikk som produktet av antallet i hver haug. Summen blir altså antall strikk vi hadde til å begynne med. Dette synes jeg gjorde det hele både mer kortfattelig og anskuelig.

Dette var mye mer forståelig, ja, og å forklare det på den måten var en del finere. Den geometriske løsningen var også stilig, og når en setter det opp på den lure måten er det ikke så vanskelig å se hvordan en o svarer til et utvalg av to bestemte steiner.

Slenger ut en litt vanskeligere oppfølger:

i) [tex]\sum _ {i=0}^n 2^i {n \choose i } {n-i \choose \lfloor \frac {n-i} 2 \rfloor} = { 2n+1 \choose n} [/tex]