Kombinatorik pk, ht 2000

Kursledare

Kurslitteratur

Veckoschema

1. Den kombinatoriska metaprincipen, additions- och muliplikationsprinciperna, incidensräkning, urval, permutationer.

   Text

   1.1-1.3

   Övningar

   1.2:11,35,36, 1.3:7,21,26,31

2. Mängder, funktioner, urval med repetition, lådprincipen.

   Text

   1.4, 5.1-5.3, 5.5

   Övningar

   1.4:15,16, 5.2:3, 5.3:1,4,6, 5.5:6,7,16

3. Inklusion-exklusion ("sållprincipen"), derangemang.

   Text

   8.1-8.3

   Övningar

   8.1:7,14,19,24, 8.2:4,7, 8.3:4,9

4. Tornpolynom (= rookpolynom), förbjudna positioner, genererande funktioner.

   Text

   8.4-8.6, 9.1-9.2

   Övningar

   8.5:7,10,11, 8.Suppl:17,18, 9.1:4,5, 9.2:11,12,20

5. Heltalspartitioner, exponentiella genererande funktioner.

   Text

   9.3-9.5

   Övningar

   9.3:5,6, 9.4:5,6,10, 9.5:5

6. Linjära rekursioner.

   Text

   10.1-10.3

   Övningar

   10.1:5,8, 10.2:13,14,16, 10.3:6,11,12

7. Lösning av rekursioner med genererande funktioner, catalantal.

   Text

   10.4-10.5

   Övningar

   10.4:1,3, 10.5:1,3,6,9

8. Grafer, delgrafer, isomorfa grafer, grad, eulerstigar.

   Text

   11.1-11.3

   Övningar

   11.1:9,14, 11.2:5,6,11,12, 11.3:13,14,16,19,28,30

9. Hamiltonstigar, planaritet.

   Text

   11.4-11.5

   Övningar

   11.4:3,14,18,19, 11.5:7,8,18,19

10. Färgning, kromatiskt tal, kromatiska polynom.

    Text

    11.6

    Övningar

    11.6:7,14,16,19

11. Träd med tillämpningar.

    Text

    12.1-12.2, 12.4

    Övningar

    12.1:9,10,15, 12.2:3,4,10, 12.4:1,2

12. Kombinatoriska optimeringsproblem: kortaste stigar, minimala spännande träd.

    Text

    13.1-13.2

    Övningar

    13.1:1,2, 13.2:1,6,9

13. Flödesteori, matchningsteori.

    Text

    13.3-13.4

    Övningar

    13.3:3,6, 13.4:3,10,13

14. Repetition

Examination