Kombinatorikk (algebra)

[Magnus]

Hentet fra en eksamen i algebra på NTNU.. Noen som tar den uten bruk av Burnside?

Oppgave:
Hvor mange forskjellige måter kan vi fargelegge hjørnene i en regulær femkant, når vi har 3 ulike farger tilgjengelig og disse kan brukes så mange ganger vi vil?
To farginger regnes som like dersom vi kan få den ene fra den andre ved å rotere eller vende femkanten i rommet.

[Matematikkk]

ja, måten min er ikkje spesielt vakker, men den er kombinatorisk. Den går rett og slett ut på å telle alle muligheitar. Eg brukar (t,t,t,t,t) til å vise forma på femkanten. For eksempel vil (1,2,3,2,1) bety at vi har farge 1 først, så farge 2, 3, 2 og 1 til slutt, dei to av farge 1 vil henge saman.(alltid tuklete å føre kombinatorikk...)

1 farge: Alle fargane er like(11111), vi har tre fargar og 3 muligheitar.

2. fargar: Dersom den eine er ulik dei andre(11112), dersom to er ulike og rett ved sida av kvarandre(11122), og dersom to er ulike og ikkje rett ved sida av kvarandre (11212), alle desse tre måtane har alle 6 måtar å velge fargar på, så vi får tilsaman 18 kombinasjonar med 2 fargar.

3 fargar: Her må vi holde tunga beint i munnen, men vi får til sammen 5 måtar: (11123), (11213), (11223), (12213) og (12123).
Ved (11123) er farge 2 og 3 symmetriske, så det finst berre 3 slike(treng berre velge farge nr 1), akkurat slik er det også med (11213), (11223) og (12123) også. Ved (12213) er ingen av fargane symetriske, så vi får her 3!=6 muligheitar. Tilsaman med 3 fargar får vi 3*4+6=18 fargar.

Så antal måtar å farge 5-kanten på er lik 3+18+18=39.

Noken som har en bedre kombinatorisk måte? Vil du vise oss Burnside Magnus?

[mrcreosote]

Jeg tok det fra andre sida: (abc) skal bety at vi har a med en farge, b med en annen farge og c med en tredje. Hvis vi da ser på mulighetene hvor [tex]a\geq b\geq c[/tex], teller fargelegginger og ganger opp med antall permutasjoner etterpå burde vi havne samme sted. Vi har disse mulighetene:

(500): 1 måte, 3 permutasjoner: 3.
(410): 1 måte, 6 permutasjoner: 6.
(320): 2 måter (de som er to ved siden av hverandre eller ikke), 6 permutasjoner: 12.
(311): 2 måter som over, 3 permutasjoner: 6.
(221): 4 måter (les forrige post, dette er den vanskeligste), 3 permutasjoner: 12.

39 her også.

Kanskje mye samme tankegodset, men det angripes fra motsatt hold.

Burnside fordrer kunnskap til litt gruppeteori og er en ganske morsom anvendelse av dette. Kort fortalt handler det i dette tilfellet om hvor mange fargelegginger av femkanten som holdes invariante om vi gjør 1 av de 10 operasjonene flikke 108 grader (5 stykk) og speile om en akse (også 5). (Fikk 39 med denne metoden også.)

Får du broder'n i gang med noen mattekurs igjen snart?

[Magnus]

Jada 39 er korrekt svar det. Burnside er som mrcreosote skriver her. Hvis du vil se hvordan fasit løste den med burnside, titt på:
http://www.math.ntnu.no/emner/TMA4150/2007v/lfeks06.pdf

Oppgavetekst: http://www.math.ntnu.no/emner/TMA4150/2007v/tman.pdf (TMA4150)
http://www.math.ntnu.no/emner/TMA4150/2007v/man.pdf (MA2201)

[mrcreosote]

Det så ut som en veldig grei eksamen i et introkurs i abstrakt algebra. Nå er vel kursa i Trondheim på 7.5 poeng, men sammenlign med http://www.math.uio.no/academics/eks/MA ... 2006_1.pdf som vel blir tilsvarende i Oslo. Riktignok 10 studiepoeng her, men det var ganske stor forskjell syns jeg. Kurset brukte Fraleigh og skulle dekke det meste av boka bortsett fra del VII-IX og en del av daggerkapitla. (Men med Sylow.)

[Magnus]

Har sett på den før. Joa. Vi har kun kap. 1-23 samt 26 da(med unntak av kap 7 og 12). De som har MA-fag (hovedsaklig de på matematikk bachelor) har da Sylow-teoremene, mens vi på TMA (siving-varianten) har generering av endelige kropper i steden. Hadde faktisk eksamen i går. Var ikke så vanskelig, men var en deloppgave jeg ikke fikk til som Knut angivelig skal ha klart for 2 år siden.. : )

Det må dog huskes at dere kun har 3 fag i semesteret da, og dermed sikkert kjører på med større pensum. Ser jo dere har Galoisteori også.


edit: Kom på at jeg hadde skrevet et sammendrag av pensum.. http://folk.ntnu.no/botnan/dokumenter.jsp

[Magnus]

Ok. Først nå slo det meg at du er Vidar, haha.

[Matematikkk]

hehe, bra gjetta, det er meg;)