Kombinationer och permutationer – Kombinatorik
2013-12-10 Av Simon Rybrand 12 kommentarer
i 3 stycken blogginlägg har jag här på Matematikvideo.se introducerat det område inom den diskreta matematiken som kallas för kombinatorik. Du hittar det första inlägget här (introduktion och lådprincipen) och det andra här (additions- och multiplikationsprincipen).
I det här sista inlägget tänkte jag att vi skulle kika på det som kallas för kombinationer och permutationer.
Kombination och permutation РVilka fr̴gor besvaras?
De flesta principer och metoder inom kombinatorik handlar framförallt om att besvara frÃ¥gan ”PÃ¥ hur mÃ¥nga sätt?”. Man vill ofta ta reda hur mÃ¥nga sätt som nÃ¥got kan göras, väljas ut eller grupperas om. Kombinationer och permutationer handlar framförallt om att man vill avgöra pÃ¥ hur mÃ¥nga sätt som nÃ¥got kan väljas ut och här är det viktigt att hÃ¥lla koll pÃ¥ om urvalet görs pÃ¥ ett ordnat eller oordnat vis. Hur skall man dÃ¥ förstÃ¥ det här med ordning eller oordning i det här sammanhanget?
För att förklara det här så är det nog enklast att ta ett exempel. Låt säga att vi vill välja ut 3 besättningsmän till en båt ur en grupp på 20 personer.
Ett alternativ är då att välja ut personer till bestämda platser, tex till kapten, styrman och maskinist. Då säger man att urvalet skall ha en bestämd ordning och då kan vi använda det som kallas för permutationer för att veta hur många sätt som detta kan göras på.
Om urvalet inte görs på ett sätt där det får bestämda platser så kallas det istället för en kombination. Här kan man från exemplet säga att man istället bara väljer ut 3 besättningsmän och att dessa inte har några bestämda platser.
Hur beräknas permutationer och kombinationer?
För att kunna göra beräkningar på kombinationer och permutationer så behöver man känna till det som kallas för fakultet och som betecknas ! (utropstecken). Om man exempelvis skall beräkna 4! så multipliceras alla heltal från 4 till 1 med varandra för att få resultatet. Några exempel kan då vara:
- $ 4! = 4â‹…3â‹…2â‹…1 = 24 $
- $ 5! = 5â‹…4â‹…3â‹…2â‹…1 = 120 $
- $ 0! = 1 $ (definieras på detta vis).
För att sedan beräkna en permutation (urvalet är ordnat) så gäller följande
- $ P(n,k) = \frac{n!}{(n-k)!} $ – Detta innebär att du beräknar antal permutationer av k element bland n element.
Så om vi skulle välja 3 besättningsmän ur en grupp på 20 personer till bestämda platser så kan detta göras på
- $ P(20,3) = \frac{20!}{(20-3)!} = \frac{20!}{17!} = 20⋅19⋅18 = 6840 $ olika sätt.
När du skall beräkna en kombination (urvalet är oordnat) så görs detta istället enligt
- $ C(n,k) = \frac{n!}{k!(n-k)!} $ – Detta innebär att du beräknar antal kombinationer av k element bland n element.
Så om vi skulle välja 3 besättningsmän ur en grupp på 20 personer där ordningen inte spelar någon roll så kan detta göras på
$ C(20,3) = \frac{20!}{3!(20-3)!} = \frac{20⋅19⋅18}{6} = 1140 $ olika sätt.
Träna på att se när olika principer går att använda
När man håller på med kombinatorik så är det sällan som algebran eller aritmetiken är särskilt krånglig eller kräver särskilt många steg. Istället så är den största utmaningen oftast att förstå själva frågan och vilken av alla principer som går att använda. Ett viktigt moment när du jobbar med denna typ av matematik är därför att sätta sig in i alla principer, försöka se skillnader mellan dessa och att träna mycket på dessa.
Med de här avslutande orden om kombinatorik så avslutar vi denna lilla bloggserie i 3 delar. Hoppas att du som letar grundläggande information i detta ämne har lärt dig något nytt och att du fått en bra övergripande bild av området.
Jag har kommit fram till att det finns 120 kombinationer totalt om personerna måste gå till olika hus. Men sedan vet jag inte hur jag ska göra för att få exempelvis ett rätt, eller två rätt osv. Tror du att det kan finnas någon formel som innehåll r och p för att få reda på sannolikheten för till exempel ett rätt eller två rätt av fem personer osv? Tack för ditt snabba svar.
Hej!
Sitter just nu med en uppgift som handlar om sannolikhet/kombinatorik och den lyder såhär:
”I programmet Vem bor här? ska man para ihop fem personer med rätt hem, och i programmet Upp till bevis! ska man bara ihop sex personer med rätt yrke. Vad är sannolikheten att fÃ¥ r rätt om du ska para ihop p personer?”
Här försökt lösa uppgiften, men jag kommer verkligen inte framåt så jag undrar om du har något knep för att komma fram?
Hej!
På vilket sätt har du försökt att lösa uppgiften?
Att sätt in r personer på deras rätta plats kan bara göras på ett sätt. De övriga kan dock sättas in på olika sätt.
Sedan får du fundera på hur många sätt (kombinationer) som finns totalt.
Hej
kul sida, jag hÃ¥ller pÃ¥ med en avancerad app, där jag kräver länkar, där jag behövde ta reda pÃ¥ hur mÃ¥nga olika variationer/sätt jag kunde skapa en viss länk pÃ¥ utifrÃ¥n vissa förutsättningar (dvs antalet tecken). Eftersom mina matematiska kunskaper pÃ¥ just kombinatoriken var lite ringrostiga sÃ¥ var det kul att jag fann detta, det hjälpte. Nu vet jag vad konsekvensen blir och vilken säkerhet jag kan fÃ¥ ut av att veta antalet kombineringar. Ville bara dela med mig av detta sÃ¥ att även andra kan se att matematik kommer till mer pass ibland än att räkna in antalet barn pÃ¥ dagis, räkna ihop kostnad för mjölk och bröd ”INNAN” man gÃ¥r till snabbkassan. Just kombinatoriken är en välbehövande komponent i rätt mÃ¥nga tillämpade fall.
Kul att det här hjälpte dig i ett konkret fall och att du delade med dig av detta!
Sitter med en uppgift i kombinatorik jag inte alls förstår hur jag ska lösa och önskar en hjälpande knuff i rätt riktning.
”Hur mÃ¥nga sjusiffriga tal kan man bilda med fyra ettor och tre tvÃ¥or om första siffran mÃ¥ste vara 1 och sista siffran mÃ¥ste vara 2?”
Söker inte själva svaret utan hjälp med att förstå hur jag ska lösa uppgiften.
Hej
DÃ¥ har du alltsÃ¥ 5 ”tomma” platser där du skall placera ut 3 ettor och 2 tvÃ¥or, vi kan visualisera talet pÃ¥ följande vis:
1 â–¡ â–¡ â–¡ â–¡ â–¡ 2
Vi kan först ta reda på hur många sätt som vi kan placera ut 3 ettor på fem platser där ordningen inte spelar någon roll,dvs vi beräknar kombinationen
$ C(5,3) = \frac{5!}{3!(5-3)!} =10 $
Det finns alltså 10 olika sätt att placera ut ettorna.
Om vi hade tänkt att vi istället skulle placera ut tvåorna först så hade det även då funnits 10 olika vis då
$ C(5,2) = \frac{5!}{2!(5-2)!} =10 $
Detta är även vårt svar då de övriga talen är samma tal. Dvs om vi placerar ut ettorna på ett sätt så kommer det inte gå att ändra kombinationen eftersom att det inte spelar någon roll för talet om vi byter ordningen på tvåorna.
Tack för förklaringen nu förstår jag vad det handlar om! Jag har dock en fråga för hur man kan räkna ut antalet olika sätt för större fakulteter. Kan du förklara hur du går tillväga när du räknar ut 20!/17!= 20*19*18? Finns det någon räkneregel? Tack på förhand!
Hej
Hade nog tänkt på följande vis:
$ \frac{20!}{17!}= \frac{20â‹…19â‹…18â‹…17â‹…16â‹……â‹…2â‹…1}{17â‹…16â‹…15â‹……â‹…2â‹…1} $
Här kan du förkorta med alla faktorer från 17 och nedåt i både täljare och nämnare så att det som återstår är $ 20⋅19⋅18 $.
Hoppas att resonemanget hjälper dig vidare
Tack Simon för lättförståelig förklaring av urvals matematiken.
Hej.
Har själv sjukt svårt med matten. Läste matte 1b kursen HT-13 och skulle idag 27/12 göra np men mailade min lärare och skrev att jag känner att jag behöver läsa om kursen.
Tänker nu läsa kursen VT-14 och har redan ångest över hur det kommer gå. Just matte har jag alltid haft svårt för.
Ska bli spännande att följa denna serie/blogg!
Hej,
Kul att du hittat hit och vill följa bloggen. Bra ändå att du verkar ta tag i din kurs och vilja klara av den, det är första steget mot att lyckas med sina matematikstudier. Då får man mer motivation till att orka träna och öva mycket på matematik. Lycka till nu inför våren!