Kombinatorik (5hp), VT 2010

Kurskod 1MA020.    Kursplan   Studentportalen.

Lärare: Svante Janson

Kurslitteratur

Av boken ingår följande avsnitt: Som bredvidläsning rekommenderas ett kompendium av Sten Kaijser. (Detta täcker dock inte hela kursen. Dessutom finns i detta exemplar vissa besvärande tryckfel: bl.a. saknas ett lemma på s. 8 och en sats på s. 9, liksom sidorna 12-14.)

Schema        Denna vecka

Tentamen

Kontrollera tentamensschema för ev. ändringar.

Inlämningsuppgifter

Inlämningsuppgifter kommer att delas ut 3 gånger under kursen. Dessa utgör del av examinationen och skall lösas individuellt. Korrekta lösningar ger bonuspoäng vid ordinarie tentamenstillfället, med högst 1 poäng per omgång (totalt högst 3 bonuspoäng; summan avrundas nedåt till heltal). Lösningar kan lämnas vid undervisningen eller i mitt postfack på Ångström, senast angiven tid.
  1. 15 februari     svar.
  2. 2 mars kl. 15     svar.
  3. 11 mars kl. 10.15    svar.

Föreläsningar

Innehåll i stora drag, med hänvisningar till avsnitt och speciellt viktiga satser i Brualdi.
Rekommenderade övningar (ur Brualdi) anges med "Exerc." På räkneövningarna går jag (så långt jag hinner) igenom lösningar till dessa och andra problem, angivna nedan.
  1. 18/1: Inledning, mängdlära, additionsprincipen, multiplikationsprincipen. §1, 2.1.
  2. 19/1: Subtraktionsprincipen, divisionsprincipen, permutationer, kombinationer. §2.2, 2.3. Th. 2.2.1, 2.3.1, Cor. 2.3.2, Th. 2.3.3, 2.3.4. Exerc. Ch. 2: 1, 2, 3.
  3. 21/1: Permutationer och kombinationer med flera likadana objekt. Klassisk sannolikhetsteori. §2.4, 2.5, 2.6. Th. 2.4.2, 2.5.1. Exerc. Ch. 2: 37, 45, 60.
  4. 22/1: Räkneövning. Exerc. Ch. 2: 1, 2, 3, 8, 9, 13, 15, 21, 23, 36, 37, 39, 41, 45, 56, 57, 60, 63.
  5. 25/1: Dirichlets lådprincip. §3.1, 3.2. Th. 3.1.1. Exerc. Ch. 3: 4, 5, 8, 11, 14, 18.
  6. 27/1: Binomialkoefficienter. §5.1, 5.2, 5.4. Th. 5.2.1, 5.4.1. Exerc. Ch. 5: 3, 4, 5, 6, 7, 9, 13, 19, 23
  7. 29/1: Räkneövning. Exerc. Ch. 3: 4, 5, 8, 11, 14, 18; Ch. 5: 3, 4, 5, 6, 7, 9, 13, 19, 20, 23, 25, 38, 39, 40
  8. 1/2: Inklusion-exklusion, oordningar. §6.1, 6.3. Th. 6.1.1, Cor. 6.1.2. Exerc. Ch. 6: 1, 2, 3, 6, 11, 32.
  9. 3/2: Inklusion-exklusion. §6.2, 6.3. Exerc. Ch. 6: 7, 9, 12, 15, 29
  10. 5/2: Räkneövning. Exerc. Ch. 6: 1, 2, 3, 6, 7, 9, 11, 12, 14, 15, 17, 29, 32; Ch. 5: 25, 38, 39, 40.
  11. 8/2: Rekursion. §7.1, 7.4. Th. 7.4.1. Exerc. Ch. 7: 2, 3, 4, 9, 11, 12
  12. 10/2: Rekursion. §7.4, 7.5. Th. 7.4.2. Exerc. Ch. 7: 31, 35, 37, 39, 40, 42.
  13. 11/2: Räkneövning. Exerc. Ch. 7: 2, 3, 4, 9, 11, 12, 31, 35, 37, 39, 40, 42.
  14. 15/2: Genererande funktioner. §7.2. Exerc. Ch. 7: 13, 16, 17, 19, 48.
  15. 17/2: Genererande funktioner. §7.2, 7.3. Exerc. Ch. 7: 22, 25, 27, 51.
  16. 18/2: Räkneövning. Inlupp 1 och Exerc. Ch. 7: 13, 16, 17, 19, 22, 25, 27, 48, 51.
  17. 2/3: Catalantal. §7.6, 8.1. Exerc. Ch. 8: 1, 36.
  18. 3/3: Räkneövning. Inlupp 2 och Exerc. Ch. 5: 25, 38, 40; Ch. 8: 2.
  19. 5/3: Räkneövning. Tenta 17/3 2009.
  20. 11/3: Räkneövning. Inlupp 3 och tenta 20/8 2009.

En kort ordlista

Detta är ett litet komplement till Anders Vretblads allmänna matematiska ordlista.
Engelska Svenska
binomial coefficient binomialkoefficient
combination kombination
derangement oordning
exponential generating function exponentiellt genererande funktion
generating function genererande funktion
inclusion-exclusion principle inklusion-exklusionsprincipen
multinomial coefficient multinomialkoefficient
multiset multimängd
permutation permutation
pigeon hole principle lådprincipen (postfacksprincipen)
recurrence relation rekurrensrelation
subset delmängd