Jeg må bare bite i det sure eplet her og spørre om hjelp til ei tenkeoppgave jeg ikke får til. Det er snakk om oppgave 4.2.27 i Kalkulus.
Man har k farger til rådighet og skal fargelegge en sirkel delt opp i n nummererte sektorer slik at ingen nabosektorer har samme farge. La [tex]a_n[/tex] være antall måter dette kan gjøres på. Man skal vise at
[tex]a_{n+1} + a_n = k(k-1)^n[/tex] for [tex]n \ge 2[/tex].
Kombinatorikk
Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Greit, tror jeg endelig fikk til denne allikevel. Skal poste tankegangen min.
Hvis vi ser bort fra den restriksjonen at sektor 1 og sektor (n+1) ikke kan være samme farge, kan vi fargelegge en sirkel med n+1 sektorer på [tex]k(k-1)^n[/tex] måter: Vi har k fargemuligheter på den første fargesektoren, så [tex]k-1[/tex] fargemuligheter på den neste sektoren, fordi fargen på sektoren før ikke kan brukes. Den tredje sektoren vil på samme måte ha k-1 fargemuligheter, og slik fortsetter det til den (n+1)-te sektoren, altså vil det være [tex]k(k-1)^n[/tex] muligheter. Men vi må trekke fra de mulighetene der sektor 1 har samme farge som sektor (n+1). Vi vet at sektor n ikke kan ha samme farge som sektor (n+1), og vil derfor heller ikke ha samme farge som sektor 1. Men nå klipper vi bort sektor (n+1) slik at sirkelen har bare n sektorer. Denne sirkelen har ingen nabosektorer med samme farge, altså er det [tex]a_n[/tex] kombinasjoner av slike sektorer. Vi må altså ta totalt antall muligheter (når vi lar sektor 1 ha samme farge som sektor (n+1)) som da er [tex]k(k-1)^n[/tex] og trekke fra de ugyldige mulighetene, som er [tex]a_n[/tex], dette gir
[tex]a_n+1 = k(k-1)^n - a_n[/tex]
og differenslikningen følger.
Men holder denne forklaringen vann?
Hvis vi ser bort fra den restriksjonen at sektor 1 og sektor (n+1) ikke kan være samme farge, kan vi fargelegge en sirkel med n+1 sektorer på [tex]k(k-1)^n[/tex] måter: Vi har k fargemuligheter på den første fargesektoren, så [tex]k-1[/tex] fargemuligheter på den neste sektoren, fordi fargen på sektoren før ikke kan brukes. Den tredje sektoren vil på samme måte ha k-1 fargemuligheter, og slik fortsetter det til den (n+1)-te sektoren, altså vil det være [tex]k(k-1)^n[/tex] muligheter. Men vi må trekke fra de mulighetene der sektor 1 har samme farge som sektor (n+1). Vi vet at sektor n ikke kan ha samme farge som sektor (n+1), og vil derfor heller ikke ha samme farge som sektor 1. Men nå klipper vi bort sektor (n+1) slik at sirkelen har bare n sektorer. Denne sirkelen har ingen nabosektorer med samme farge, altså er det [tex]a_n[/tex] kombinasjoner av slike sektorer. Vi må altså ta totalt antall muligheter (når vi lar sektor 1 ha samme farge som sektor (n+1)) som da er [tex]k(k-1)^n[/tex] og trekke fra de ugyldige mulighetene, som er [tex]a_n[/tex], dette gir
[tex]a_n+1 = k(k-1)^n - a_n[/tex]
og differenslikningen følger.
Men holder denne forklaringen vann?