Matte Diskret - Sannolikhetslära och kombinatorik
Kombinatorik
Multiplikationsprincipen
Multiplikationsprincipen säger att om man vill få fram det totala antalet möjligheter så multiplicerar man antalet möjligheter i de olika stegen
Tjusig regel, men vad innebär den egentligen? Vi tar ett exempel för att förklara det närmare.
Joakim och några av hans kompisar beslutar sig för att gå och äta på restaurang en kväll för att fira att det gick så bra på deras stora matteprov. De tänker slå på stort med både för-, huvud- och efterrätt. När Joakim slår upp menyn ser han att det finns 4 förrätter, 3 huvudrätter och 5 efterrätter att välja mellan. För en kort sekund funderar han: “Undrar på hur många olika sätt jag kan beställa min mat?”
För att svara på denna fråga så kan vi utnyttja multiplikationsprincipen. Enligt den ska vi alltså få fram antalet möjliga kombinationer genom att vi multiplicerar antalet alternativ ur varje kategori med varandra:
Det finns alltså 60 olika sätt som han kan beställa sin mat på.
Per ska välja kläder inför skolfotograferingen. På hur många sätt kan han kombinera sin klädsel om han står och väljer mellan 5 T-shirts, 3 jeans och 6 sneakers?
Enligt multiplikationsprincipen ska vi multiplicera antalet möjliga val med varandra:
Svar: Per kan kombinera sin klädsel på 90 olika sätt.
Permutationer
Karin är kläddesigner och deltar med tre modeller (A, B och C) i en modevisning. Inför visningen måste hon bestämma i vilken ordning hon vill visa upp sina tre plagg. På hur många olika sätt (olika ordningsföljder) kan plaggen visas upp?
Ett sätt att räkna ut detta är att skriva upp alla olika ordningar: ABC, ACB, BAC, BCA osv. men om det nu hade gällt sju modeller/plagg hade det snabbt blivit ett evighetsgöra. Som väl är finns det ett enkelt sätt att resonera kring det hela.
Vi tittar på hur många platser en modell kan stå på. Modellen kan antingen gå ut först, som andra person eller som sista person, 3 platser med andra ord. På hur många sätt kan vi välja den person som ska gå först? Vi har här alla tre modeller till förfogande så svaret blir 3 sätt. När vi nu ska välja vem som ska gå efter den första personen har vi bara 2 personer kvar då den tredje redan står på första platsen. Det finns alltså 2 sätt att välja nu. Då sista platsen ska fyllas har vi bara en person kvar, valet av denna person till den sista platsen kan ske på 1 sätt.
Det totala antalet sätt att ordna de 3 modellerna är . Vi säger att det finns 6 varianter eller permutationer.
Denna metod kan som väl är tillämpas på liknande situationer oavsett antal. Hade det handlat om 4 modeller hade vi kunnat skriva:
När vi räknar på detta sätt räknar vi ut den s.k. n-fakulteten.
n-fakultet
n-fakultet skrivs som n! och definieras som antalet sätt att ordna n element:
och gäller för alla heltal n > 0
n är antalet valmöjligheter.
Situationen liknar den som vi beskriver för multiplikationsprincipen, men det är en viktig skillnad. Här gör vi flera val ur samma grupp, alltså när vi väl har valt en utav personerna kan denne inte väljas igen – det första valet påverkar det andra valet osv. Antalet möjliga val minskar alltså med en person för varje val vi gör. I exemplet med multiplikationsprincipen gör vi ett val ur förrättsgruppen, men det valet påverkar inte antalet huvudrätter som vi sedan ska välja ur.
Beräkna
a) 6! b) c)
a)
Enligt regeln för n-fakultet ska vi multiplicera alla tal upp till 6 med varandra:
b)
Enligt räknereglerna prioriteras n-fakultet före division. Med andra ord räknar vi ut n-fakulteten för täljare respektive nämnare genom att multiplicera alla tal upp till 24 respektive 18 med varandra. Först därefter kan vi utföra divisionen.
c)
Samma tillvägagångssätt som i uppgift b. n-fakulteten först, sedan divisionen.
Svar: a) 720 b) 96909120 c) 15120
n-fakultet på grafräknaren
Denna övning finner du under grafräknarsektionen. För att läsa vidare om hur man gör, klicka här.
nPr
Vi fortsätter med vårt exempel om Karin och hennes modeller. Om situationen istället hade varit att Karin hade en klänning, en byxdress och en kjol att visa upp och skulle välja ut 3 av 7 tillgängliga modeller som skulle få visa upp dessa, på hur många sätt kan valet ske om man först väljer den som ska bära klänningen, sedan den som ska bära byxdressen och sist den som ska bära kjolen? Notera att modellerna bara kan väljas en gång – en modell kan inte gå två gånger.
Här kan vi inte tillämpa n-fakultet för att räkna ut antalet varianter. n-fakulteten ger antalet varianter då man ordnar alla 7 tillsammans. Nu är det ju bara 3 av de 7 som ska ordnas. Vi säger att 3 element av 7 element väljs.
Första valet kan ske på 7 olika sätt och efter att första modellen är vald så finns det bara 6 kvar att tillgå, och slutligen efter andra valet finns det 5 kvar att välja mellan.
Antalet sätt att välja blir därmed:
Matematiskt uttrycker man sig som: antalet permutationer av 3 element valda bland 7 element är .
Uttrycket innehåller 3 faktorer (3 valda element) som har valts bland de 7 tillgängliga, något som uttrycks på engelska som 7P3, eller mer vanligt: nPr.
Även denna metod är generaliserbar så vi kan skapa ett uttryck som går att använda för alla tal och blir extra smidigt när det blir stora tal och mycket siffror:
Antalet permutationer av r element valda bland n element är
Ett fotbollslag består av 25 spelare, på hur många olika sätt kan urvalet av spelare se ut under en fotbollsmatch om det får vara 11 spelare ute på plan samtidigt?
Precis som vi sagt tidigare så gäller det att när en spelare är vald att spela så har vi “förbrukat” denne, dvs. det är en mindre att välja bland när man har valt första spelare, två mindre att välja mellan när man valt andra spelaren osv.
Det får bara vara 11 spelare på planen, men vi har 25 att välja mellan. Vi ska alltså välja 11 element (r) bland 25 element (n).
Vi använder oss av formeln ovan och ersätter n med 25 och r med 11:
Det som sker inuti parentesen prioriteras före n-fakulteten.
Det man egentligen gör med denna formel är att man beräknar n-fakulteten för 25 och sedan räknar bort n-fakulteten för de 14 som inte väljs ut till att spela. Borträkningen sker genom division.
Svar:
nPr på grafräknaren
Denna övning finner du under grafräknarsektionen. För att läsa vidare om hur man gör, klicka här.
Permutationer med flera lika element
Låt säga att vi ska beräkna hur många varianter det finns av ordet QQRRRSSST. Först ser vi efter hur många bokstäver det är totalt, 9 stycken. Med andra ord finns det permutationer där en del av dem är likadana. Vi ser att vi har 2 Q:n, två bokstäver kan permuteras på sätt. Om vi säger att Q hade varit den enda bokstaven som det fanns fler av så skulle antalet permutationer ha reducerats med en faktor 2. Men vi ser att det finns 3 R och 3 S där permutationerna reduceras med en faktor 6 (3!) för vardera bokstav.
Formeln för antalet ord som kan bildas av ordet QQRRRSSST blir:
Hur många permutationer får vi ut ur ordet MATEMATIK?
Matematik består av 9 bokstäver. Totalt har vi permutationer där några är likadana eftersom det finns dubletter av bokstäver i ordet. Dubletterna är 2 stycken M, 2 stycken A och 2 stycken T. Vardera bokstavstyp reducerar permutationerna med en faktor 2. Vi skriver in 9! i täljaren och reducerar genom att skriva in tre stycken 2! multiplicerat med varandra i nämnaren:
Svar: Det blir 45 360 permutationer.
Kombinationer
När vi ska välja ut r element bland n element och ordningen på dem inte spelar någon roll, så kan vi räkna ut hur många kombinationer det kan bli. Det enda som är intressant är vilka som blir valda. Låt säga att vi ska välja ut 3 av 4 personer (Daniel, Elin, Freddy och Gustav), på hur många sätt kan detta val ske om vi bortser från ordningsföljden när vi väljer dem?
Totalt finns det varianter/permutationer av de 3 elementen som vi väljer ut:
| DEF | DFE | EDF | EFD | FDE | FED |
| DEG | DGE | EDG | EGD | GFE | GEF |
| DFG | DGF | FDG | FGD | GDF | GFD |
| EFG | EGF | FEG | FGE | GEF | GFE |
Men, precis som jag nyss sa, grejen med kombinationer är att ordningen på dem inte spelar någon roll. Med andra ord räknas DEF och DFE som “samma” variant. Om du tittar noga i tabellen med de 24 möjligheterna så ser du att kombinationerna för respektive rad består av samma bokstäver: översta raden har D, E och F i olika varianter, andra raden har D, E och G, tredje raden D, F, G och nedersta raden har E, F och G.
Alltså, trots att det finns 6 varianter per rad så är vi bara intresserade av innehållet för varje rad, inte i vilken ordning innehållet står, vilket innebär att det finns 4 olika möjligheter (4 rader med olika innehåll).
För varje rad ser vi 6 olika varianter av 3 element, med andra ord, 3 element kan ordnas på olika sätt. För att matematiskt få fram antalet möjliga kombinationer måste vi reducera antalet möjligheter med en faktor 6 (reducera med det antal sätt som elementen kan ordnas).
Det beräknas på detta vis:
Om vi tillämpar detta på vårt modellexempel. Karin ska välja ut 3 modeller av 7 som ska få visa upp hennes plagg, men det spelar ingen roll i vilken ordning plaggen visas upp.
Vi säger att det finns 35 kombinationer när man bland 7 element väljer ut 3 och detta skrivs som:
och utläses “7 över 3″.
Formeln för kombinationer är följande:
Antalet kombinationer av r element valda bland n element är
Förklaring till hur man kommer fram till formeln
För dig som bara vill acceptera formeln och kunna räkna med den är denna förklaring överflödig, gå istället vidare till exemplet. Egentligen är det hela ganska enkelt. Formeln är resultatet av att man har förlängt bråket så det blir smidigare att använda formeln när det handlar om större tal. Låt säga att vi ska välja ut 100 personer bland 250 möjliga personer. Istället för att skriva hela raddan på grafräknaren:
så vore det ju smidigt med något man lätt kan knappa in.
Vi tar exemplet med
Det vore ju himla trevligt om vi bara kunde skriva istället för att rabbla upp alla de som ska multipliceras. Det går att göra genom att vi förlänger bråket med .
4! står för det som är kvar ifall vi skulle ha fortsatt att multiplicera ända ner till 1. . motsvarar ju inledningen av de multiplikationer som man gör för 7!. Om dessa multipliceras med 4! så är det precis som när man beräknar 7!.
som ses i regelrutan innebär att vi multiplicerar antalet valda element i n-fakultet med det antal som inte blev valda i n-fakultet.
I en klass på 30 elever ska man ta ut 14 stycken till ett innebandylag. På hur många olika sätt kan det ske utan hänsyn till ordningen?
Vi har här n = 30 element, och bland dem ska vi välja ut r = 14 element. Sätt in värdena i formeln för antalet kombinationer:
Svar: Uttagningen kan ske på 145 422 675 olika sätt.
Kombinationer på grafräknaren
Denna övning finner du under grafräknarsektionen. För att läsa vidare om hur man gör, klicka här.
21 februari 2012 @ 3:07
Gött!
11 juni 2012 @ 12:39
Vilket sätt är bäst om man ska räkna ut hur lång tid det tar att knäcka ett lösenord? Säg att en dator kan bearbeta 250000 ord i sekunden och lösenordet vi ska knäcka består av 10 tecken? Gemener, versaler, siffror samt 11 specialtecken? Ska man räkna ihop alla faktorer dvs 29+29+10+11=79 möjligheter per tecken. Blir det 79
11 juni 2012 @ 12:45
Ska man köra 79•78•77•76•75•74•73•72•71•70
17 juli 2012 @ 16:21
Master teoremet kanske?
17 juli 2012 @ 16:27
Programmering gör livet lättare, gjorde ett program som löste detta för ett år sedan. Men nu upptäckte jag att jag ska börja läsa sannolikhet nästa år, så JAG MÅSTE FÅ VETA HEMLIGHETEN! finns det någon som kan säga om det finns en matematisk formel för att lösa permutationer ELLER MÅSTE MAN RÄKNA BINÄRT?
13 januari 2014 @ 18:05
bra
1 juni 2014 @ 18:03
4*3*2*1 är inte lika med 6
9 februari 2015 @ 14:50
Andreas Bizzozero Nja, här spelar det ju ingen roll om du bara har 10 stycken A (t.ex) så du får 79 möjligheter på varje position. Hade du bara fått använda ett tecken en gång hade ditt exempel med 79*78*…70 stämt, men nu är ju upprepning tillåtet.
7 januari 2016 @ 7:17
I såna fall finns det 79^10 olika möjligheter förutsatt att man får använda samma tecken flera gånger.