1.1 Kombinatorik

Lådprincipen (sid 8-10)

Boken presenterar denna princip tämligen kortfattat. På engelska kallas principen för Pigeonhole principle! Wikipedia artikeln är bra och beskriver principen mer utförligt för den intresserade studenten!

Principen är hur som helst simpel:

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, för detta krävs det en del övning lite fantasi. Bokens uppgifter är inte speciellt utmanande, om vi hinner kan vi ta lite klurigare extraövningar.

Exempel 1: Om du väljer fem nummer från heltalen 1-8, då måste summan av två av dem bli nio.

Varje nummer kan koppp med ett specifikt annat för att summera till nio. Det finns totalt fyra sådana par: 1 - 8, 2 - 7, 3 - 6, och slutligen 4 - 5. Var och en av de fem numren tillhör en av de fyra paren. Enligt lådprincipen måste två av talen vara från samma par, vilka sålunda summerar till 9.

Lös samtliga uppgifter.

Multiplikations- och additionsprincipen (sid 11-14)

Exempel 2: 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.

Exempel 3: Hur många olika registrieringsskyltar kan det finnas i det Svenska systemet om man bortser från de förväxlingsbara I,Q,V,Å,Ä,Ö?

Bokstaverna kan väljas på 23 sätt. I,Q,V,Å,Ä,Ö går bort. Siffrorna kan väljas på 10 sätt. 0-9. Enligt multiplikationsprincipen finns $n = 23\cdot 23\cdot 23\cdot 10\cdot 10\cdot 10 = 12\,167\,000$

Lös samtliga uppgifter utom 1130 och 1132.

Permutationer (sid 15-18)

En permutation är en "uppräkning" av en mängd element/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

$\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

$\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" 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 1136, 1137b, 1139a, 1141, 1144 och så många b- och c-uppgifter ni orkar.

Kombinationer (sid 19-22)

I förra avsnittet räknade vi antalet sätt att ordna $k$ element/objekt 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 utval kallas en kombination. Tekniken är att man först räknar antalet permutationer

$\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/objekt bland $n$ som

\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.

Jag har satt ihop en kort sammanfattning av de nya begreppen i figuren nedan och illustrerat det med exemplet att välja ut 2 element/objekt av 6 tillgängliga. De grönmarkerade rutorna i figurerna representerar då de aktuella urvalen.



Lös 1153, 1154, 1155, 1156, 1157, 1159, 1160 eventuellt de lite klurigare 1161 och 1162 .

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

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

$\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 samtliga uppgifter. 1172, 1178

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 samtliga uppgifter. 1182

Binomialsatsen (sid 30-34)

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

$\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

$\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

$\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 eventuellt 1197 (tänk gärna ut ett kombinatoriskt argument).

1.2 Mängdlära

Mängder - Grundbegrepp (sid 35-38)

Här handlar det mest om att lära sig en del syntax (hur man skriver). Ganska tråkigt (men nödvändigt) att lära sig. Som kuriosa kan nämnas att vad som egentligen är en mängd och hur en sådan får defineras är mycket mer intrikat än boken medger, se t.ex. Barber paradox. Lös samtliga uppgifter utom 1203c. c-uppgifterna kan hoppas om man inte har höga betygsambitioner. I 1213 är n=11 det korrekta svaret!

Lös samtliga uppgifter utom 1203c. c-uppgifterna kan hoppas om man inte har höga betygsambitioner. I 1213 är n=11 det korrekta svaret!

Mängdoperationer (sid 39-40)

Här inför man en sorts "räknesätt" på mängder, nämligen union, snitt, differens och komplement. Man noterar att för att komplementet ska ha mening måste grundmängden vara klar, för de övriga är det inte nödvändigt.

Lös samtliga uppgifter, c-uppgiften är inte så svår. I 1227d ska den sista parentesen sitta efter B:et inte efter C:et.

Venndiagram (41-44)

Eftersom mängder kan ses som påsar med element i kan man tänka sig att representera dem grafiskt som "plana påsar". Man ritar helt enkelt en mängd som en cirkel (eller annan sluten kurva) och tänker sig att elementen ligger inuti cirkel. Ett finare namn för dessa cirklar är Venndiagram (efter John Venn). Ritar man lämpligt kan man illustrera snitt, unioner, komplement etc.

Lös samtliga uppgifter utom 1233, möjligen kan man göra a-uppgifterna i huvudet. I 1232 anser boken att t.ex. parallellogrammer inte är parallelltrapetser. Det är dom nog ganska ensamma om…

1.3 Grafteori

Inledning (46-49)

Ordet graf har två olika betydelser inom matematik. Det som ni är vana vid är en "grafisk bild" kopplad till en funktion, t.ex. grafen till $f(x)=x^2$. Här är det fråga om något helt annat, en graf är något som byggs upp av Hörn (eller noder) sammankopplade med Kanter. Man kan se en graf som ett sorts nätverk eller karta. Det klasssika problemet som anses ha givit upphov till grafteorin är problemet med Königsbergs broar som beskrivs på sida 46. Teorigenomgången i boken är långt ifrån fullständig, vilket naturligtvis inte heller är ett mål, men jag tänkte komlettera den lite grand här.


Begrepp    
Hörn/Nod Ett Hörn eller Nod kan ha gostyckligt många kanter som ansluter, eller ingen alls.
Kant En Kant är en förbindelse mellan två hörn.
Loop/Ögla Kant som börjar och slutar i samma hörn.
Grad

Hörn har gradtal, vilket indikerar antalet kanter som ansluter till hörnet.
Betecknas deg(A).

deg(A)=3
deg(B)=5
deg(C)=0

Vandring Förflyttning i en graf från hörn till hörn längs en eller flera kanter.
Väg

Vandring i en graf som inte passerar någon kant mer än en gång.

OBS! Hörn får passeras mer än en gång.

Eulerväg

Väg som passerar varje kant exakt en gång.

OBS! Hörn får passeras mer än en gång.

Kan ha maximalt 2 hörn med udda gradtal

Krets

Sluten väg, dvs. börjar och slutar i samma hörn.

OBS! Hörn får passeras mer än en gång.

Eulerkrets

Sluten Eulerväg

Alla hörn måste vara av jämnt gradtal

OBS! Hörn får passeras mer än en gång.

Stig Passerar inte samma kant eller hörn mer än en gång.
Hamiltonstig Passerar varje hörn exakt en gång.
Cykel Sluten stig
Hamiltoncykel Sluten Hamiltonstig

Lös a-uppgifterna och kanske något av följande 1414, 1416, 1417, 1418 (1419, 1420). Fixar ni och förstår de två sista kan ni känna er nöjda med detta avsnitt.

Några klassiska problem (50-53)

Här handlar det om Hamiltoncykler, där det är fråga om att "åka" runt i en graf så att alla noder passeras en gång innan man är tillbaka där man startade. I 1312 ska man försöka finna Hamiltoncykler. Att visa att sådan finns är enkelt, rita den, men att visa att sådan inte finns kräver ett bättre argument än "jag kom inte på någon". I handelsresandes problem vill man, i en graf med viktade kanter, finna vägen med minsta kantsumma. För detta finns ingen riktigt bra algoritm (i alla fall har man inte kommit på någon) utan man nöjer sig med en s.k. girig algoritm där man varje gång väljer den bästa kanten. Konstruera gärna en graf där denna algoritm inte leder till optimal cykel.

Lös samtliga uppgifter.

Träd (sid 54-55)

Detta är ett ganska marginellt avsnitt. Ni behöver känna till vad ett träd är och Kruskals algoritm, som man kan använda för att koppla ihop noder "på billigaste sätt". Varför algoritmen fungerar ingår inte i kursen.

Lös 1315, 1317 och eventuellt 1319. Notera att man inte behöver veta något om kemi i 1319, det handlar egentligen om att konstruera samtilga möjliga träd på n noder.