matematik-5-vt19:detaljplan

1.1 1.2 1.3 2.1 2.2 2.3 3.1 3.2 3.3 4.1 4.2 4.3

Introduktion

Kursen kan i princip delas upp i två nästan helt komplementära delar, nämligen diskret matematik och differentialkalkyl. Det sistnämnda är en påbyggnad på derivata- och integralköret i Ma4, och behandlas sist.

Första delen blir alltså diskret matematik. Det är inte fråga om något som är hemligt eller särskilt stillsamt utan snarare ett samlingsnamn för all matematik som inte inblandar kontinuitet (som t.ex. derivator och integraler gör). En översikt över delarna inom den diskreta matematiken kan man hitta här.

För att få en känsla för de delar som vi ska behandla i denna kurs kan man ögna igenom följande problem

Kombinatorik

- Hur många olika femkorts pokerhänder finns det?
- Fem personer ska ställa sig i en kö. Hur många olika köer kan dom bilda?

Mängdlära

(Snott från boken) Vid en gymnasieskola kan eleverna på naturvetenskapsprogrammet välja att läsa en eller flera av kurserna matematik 5, kemi 2 och fysik 2. 90 elever valde matematik, 82 kemi och 80 fysik. 30 elever valde matematik och kemi, 36 matematik och fysik, 34 kemi och fysik och 14 valde alla tre kurserna.
a) Hur många valde bara matematik?
b) Hur många valde bara kemi?
c) Hur många valde bara fysik?
d) Hur många av de 200 eleverna valde inte någon kurs?

Grafteori

- Kan du arrangera en promenad över Königsbergs sju broar så att varje bro passeras exakt en gång?
- Om du får lägga till en bro (var du vill), går det då?

Talteori

- Hur ser man snabbt på ett tal om det är jämnt delbart med 2, 4, 5, 6, 9?

1.1 Kombinatorik

Lådprincipen (8-10)

På engelska heter denna princip Pigeonhole_principle, och i Wikipediaartikeln kan man läsa mer om denna än vad boken presenterar.

Principen är enkel: Antag att du ska placera 5 (eller fler) föremål i 4 lådor. Då säger lådprincipen att minst en låda måste innehålla minst två föremål (tänk igenom denna formulering).

Mer allmänt, om du placerar n+1 (eller fler) föremål i n lådor så måste minst en låda innehålla minst två föremål.

Ännu mer allmänt, om du placerar $n \cdot k +1$ (eller fler) föremål i n lådor så måste minst en låda innehålla minst $k+1$ föremål. Om inte så hade vi ju haft högst $n \cdot k$ föremål, vilket vi ju INTE hade.

Principen är enkel, men det som kan vara knepigt är att bestämma vad som ska fungera som lådor och vad som ska fungera som föremål. Här krävs rutin/träning och inte sällan en dos fantasi. Bokens uppgifter sätter inte detta på sin spets, så om ni vill kan ni fundera på följande problem.

1) Du har $n+1$ olika heltal från 1 till $2n$. Visa att man kan plocka ut två som inte har någon gemensam faktor (>1).

2) Du har $n+1$ olika heltal från 1 till $2n$. Visa att man kan plocka ut två tal där det ena delar det andra.

3) Visa att det i en grupp alltid finns två personer som har lika många vänner. Vi utgår från att vänskap är ömsesidigt, dvs. om person A uppfattar person B som sin vän, så uppfattar person B också person A som sin vän.

4) Albin spelar minst en tennismatch varje dag under en fyraveckorsperiod men han spelar högst 40 matcher totalt under denna tid. Visa att det måste finnas en följd av dagar under vilka Albin spelar exakt 15 matcher.

Lös a-uppgifter efter behov, sedan (eller) b- och c-uppgifterna.

Multiplikations- och additionsprincipen (sid 11-14)

Antag att en restaurang erbjuder $p$ st förrätter och $q$ stycken varmrätter.

Om du vill välja en förrätt och en varmrätt kan detta göras på $p \cdot q$ olika sätt (multiplikationsprincipen).

Om du vill välja en förrätt eller en varmrätt kan detta göras på $p+q$ olika sätt (additionsprincipen).

Tänk efter så ni är med på detta. Lite slarvigt kan man säga att och ger multiplikation och eller ger addition.

Lös a-uppgifter efter behov, sedan 1125-1129 och 1132.

Permutationer (sid 15-18)

En permutation är en "uppräkning" av en mängd objekt i en viss ordning. Att beräkna antalet permutationer av $k$ element ur en mängd med $n$ element/objekt bygger på multiplikationsprincipen. Första elementet kan väljas på $n$ sätt, andra på $n-1$ sätt osv. till näst sista som kan väljas på $n-k+2$ sätt och det sista på $n-k+1$ sätt (tänk efter varför det inte blir $n-k$). Därmed får vi antalet permutationen av $k$ bland $n$ som

(1)
\begin{align} \; P(n,k)=n \cdot (n-1) \cdot \ldots \cdot (n-k+2) \cdot (n-k+1) = \dfrac{n!}{(n-k)!} \end{align}

där

(2)
\begin{align} n! = 1 \cdot 2 \cdot \ldots \cdot (n-1) \cdot n \end{align}

som utläses "n fakultet" (n factorial) är en praktisk beteckning.

Ett "klassiskt" (nja…) problem är att räkna antalet olika sexbokstavsord som man kan bilda av bokstäverna i ordet ANKFOT. Tydligen handlar det om $P(6,6)=6!=720$ stycken. Förresten, kan du ange ett riktigt ord som kan bildas förutom ANKFOT självt?

Lös 1137, 1139, 1140, 1141, 1145, 1146, 1147, 1148.

Kombinationer (sid 19-22)

I förra avsnittet räknade vi antalet sätt att ordna k element bland n. En sådan ordning kallades en permutation. Nu ska vi räkna antalet sätt att från $n$ element plocka ut $k$ stycken utan ordning. Ett sådant urval kallas en kombination. Tekniken är att man först räknar antalet permutationer

(3)
\begin{align} P(n,k)=\dfrac{n!}{(n-k)!}. \end{align}

Sedan noterar man att det finns $k!$ olika permutationer som ger upphov till samma oordnade utval (t.ex. ger ABC, ACB, BAC, BCA, CAB, CBA) upphov till samma oordnade urval $\{A,B,C\}$. Alltså grupperar vi ihop dessa permutationer till samma kombination och får då antalet kombinationer av $k$ element bland $n$ som

(4)
\begin{align} C(n,k)={n \choose k} = \dfrac{P(n,k)}{k!} = \dfrac{n!}{k!(n-k)!} \end{align}

där ${n \choose k}$ utläses "n över k". Inför framtiden kan man också notera att uttrycket ${n \choose k}$ dyker upp i samband med binomialsatsen och därför ibland kallas binomialkoefficient.

Utöver uppgifterna i boken kan ni fundera på

- Hur många femkorts pokerhänder finns det som innehåller

a) ett par (men inget bättre)?
b) ett tvåpar (men inget bättre)?
c) triss, färg, stege, kåk, fyrtal, färgstege (men inget bättre)?

- (Samma princip som 1162). Hur många delmängder med 5 tal bland talen $1,2,3, \ldots, 14$ har egenskapen att minst två av de fem talen är på varandra följande? T.ex. har delmängden $\{2,5,6,10,13\}$ denna egenskap men $\{1,5,7,9,12\}$ har det inte.

Lös 1153, 1156, 1158, 1159, 1160, 1161, 1162. 1162 kan lösas "snabbt" om man tänker "rätt".

Kommer du ihåg sannolikhetslära? (sid 23-25)

Kombinatorik är såklart nära förknippat med sannolikhetslära. Vill man har reda på sannolikheten beräknar man ju

(5)
\begin{align} P=\dfrac{\textrm{antalet gynnsamma utfall}}{\textrm{totala antalet utfall}} \end{align}

och talen i täljare och nämnare är ju kombinatoriska.

//Lös så många uppgifter som behövs, kanske b-uppgifterna. 1172 kan man skippa om man vill. //

Kombinatorik och sannolikhetslära (sid 26-27)

Finns inget att säga om detta mer än att det bygger på förra avsnittet.

Lös b- och c-uppgifterna.

Binomialsatsen (sid 30-34)

Hur man utvecklar (multiplicerar ihop) $(x+y)^2$ är säkert bekant; nämligen enligt kvadreringsregeln

(6)
\begin{equation} (x+y)^2=x^2+2xy+y^2 \end{equation}

Binomialsatsen är i princip en formel för att utveckla $(x+y)^n$ för ett godtyckligt positivt heltal $n$. T.ex. kan man få en kuberingsregel

(7)
\begin{align} (x+y)^3= (x+y)(x+y)(x+y)={3 \choose 0}x^3+{3 \choose 1}x^2y+{3 \choose 2} xy^2 + {3 \choose 3} y^3. \end{align}

Man inser att koefficienten framför t.ex. $xy^2$ blir ${3 \choose 2}$ genom att tänka efter på hur många sätt man kan plocka ut två y (och därmed ett x) ur de tre parenteserna. Koefficienten ${n \choose k}$ kallas binomialkoefficient.

Ett smidigt sätt att plocka fram binomialkoefficienterna är rekursivt via Pascals triangel. För att förstå att detta fungerar måste tänka igenom likheten

(8)
\begin{align} {n \choose k} = {n-1 \choose k} + {n-1 \choose k-1} \end{align}

vilket boken hjälper till med på sida 31-32. Det kombinatoriska argumentet på sida 31 är att föredra framför det algebraiska på sida 32.

Lös 1186, 1187, 1188, 1192, 1193, 1194 och 1197 (tänk gärna ut ett kombinatoriskt argument om möjligt).

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License