DANIELS MATTE 

Vad är kombinatorik?

Kombinatorik handlar om kombinationer, på hur många sätt något kan väljas ut, ordnas eller kombineras. För att lösa kombinatoriska problem är dessa verktyg bra att kunna:

 

1. Multiplikationsprincipen

2. Additionsprincien

3. Standarddragningar

 

Kombinatorik är nära besläktat med sannolikhetsläran. Inom sannolikhet räknar man med hur sannolikt det är att en händelse inträffar, till exempel att få ett udda tal vid kast med en tärning. Sannolikheten är kvoten mellan antalet gynnsamma utfall, de möjliga händelser som kan inträffa inom händelsen, och antalet möjliga utfall. Självklart gäller detta bara om alla utfall har lika sannolikhet att inträffa. (Om du har en tärning formad som en pyramid  kan vissa utfall vara vanligare än andra.) För att räkna ut antalet gynnsamma och möjliga utfall behöver du kunna kombinatorik.

 

Multiplikationsprincipen

Antalet valmöjligheter vid ett val med olika delval är produkten av antalet valmöjligheter vid varje delval förutsatt att antalet valmöjligheter vid varje val inte påverkas av tidigare delval.

 

Multiplikationsprincipen är betraktad som sann och har inget bevis. Den är ett axiom.

 

Additionsprincipen

Om en fördelning kan delas in i olika kategorier, som inte har något gemensamt ges det totala antalet fördelningar av summan av antalet fördelning i varje kategori.

 

Även additionsprincipen är ett axiom.

 

För att välja ut ett par med två objekt finns fyra fall:

 

1. Ordningen spelar roll och upprepning är tillåten. Det första objektet kan väljas på n sätt och eftersom upprepning är tillåten kan även det andra väljas på n sätt. Antalet par blir enligt multiplikationsprincipen                      .

 

2. Ordningen spelar roll men upprepning är inte tillåten. Det första objektet kan väljas på n sätt. Eftersom upprepning inte är tillåten kan det andra väljas på n - 1 sätt. Antalet par blir enligt multiplikationsprincipen n∙(n - 1) = n(n - 1).

 

3. Ordningen spelar ingen roll och upprepning är inte tilltåten. Antag att x är det sökta antalet par. Då kan vi räkna ut antalet par i (2) genom 2x, x är antalet sätt att välja ut vilka objekt som ska finnas i paret,

 

och 2 vilken positionen objekten ska ha. Alltså är 2x = n(n - 1) och x =                .       

 

Det totala antalet par är alltså                 .

 

4. Ordning spelar ingen roll och upprepning är tillåten. Vi kan dela in paren i två kategorier: (1) Antalet

 

par där objekten är olika,                 , och antalet par där objekten är lika, n. Det totala antalet par är

 

 

 

enligt additionsprincipen vilket kan förenklas till               .

 

Fakultet

Hur många sätt kan man bilda en kö med n personer?

Första personen kan väljas på n sätt, den andra personen (n-1), den tredje (n-2) … den n:te på ett sätt. Det totala antalet sätt blir enligt multiplikationsprincipen n(n-1)(n-2) … 2∙1. Den här produkten brukar betecknas n! (uttalas n-fakultet) och är produkten av alla heltal från 1 till n. Till exempel är 5 = 1∙2∙3∙4∙5 = 120. Kombinatoriskt kan vi definiera n! som antalet sätt fördela n objekt på n bestämda positioner.

 

 

Om du vill bestämma hur många sätt        något kan göras med ett visst krav kan det ibland vara lättare att bestämma,        , antalet sätt som inte uppfyller kravet och M, det totala antalet möjligheter utan krav och sedan använda sambandet                           .