# MAN 240 : Diskret Matematik

New information relevant to this year is as follows :

I have decided to follow more or less the same program as last year. Any eventual changes will be announced at lectures and on this website. Lecture notes will be written up and posted here to cover any material we discuss which is not available in the text-book.

As before, the rough plan is to divide the course into three parts as follows :

Part I : Enumerative combinatorics

Covers sections 2.4, 3.1-3.5, 4.1-4.4, 12.1-12.2, 18.3-18.6 (new edition : 6.1-6.4, 10.1-10.2, 10.4-10.5, 11.1-11.5, 19.1-19.2, 25.3-25.6)

Part II : Graph theory

Covers chapters 8-11 (new edition : chapters 15-18).

Part III : WE WON'T HAVE TIME FOR ANY PART III.

OBS ! The course will be examined by a mixture of written homeworks and a final written exam. You need 12p to pass. There will be 3 homeworks, each worth 3p. The final exam will be worth 19p. It is allowed to work in groups on the homework problems, but each person must write up their own solutions. Evidence of copying will be severely punished !! The questions on the homework will be generally be set at a higher level than those on the exam.

LECTURES AND LEKTIONER :

I expect that some (though maybe not so much, on the evidence of last year) of the time during the 9 lektioner will be used to answer your questions about the homework problems. The first homework will be ready during the week of March 29 - April 2.

I will also write up a list of suggested exercises for the övningsledare to do in advance of each lektion.

Here follows the day-by-day plan, which will be updated regularly.

DAY 1 : Monday, March 22

Lecture : Sections 3.4, 4.1, 4.2, 4.3 (new edition : 10.4, 10.5, 11.1, 11.2, 11.3).

Lektion : suggested exercises 2.4.3, 3.1.4, 3.2.1, 3.4.1, 3.5.4, 3.7.4, 4.1.7, 4.2.2, 4.3.2(iv)

(new edition : 6.4.2, 10.1.4, 10.2.1, 10.4.1, 10.5.4, 10.7.4, 11.1.7, 11.2.2, 11.3.2(iv))

DAY 2 : Wednesday, March 24

Lecture : Sections 4.4, 4.5 (Theorem 4.5.1) (new edition : 11.4, 11.5)

DAY 3 : Monday, March 29.

Lecture : 4.5 (ctd.), 12.1 (new edition : 11.2, 11.4 (ctd.), 19.1). Extra : Proof of recurrence formula for derangements ps pdf dvi tex

DAY 4 : Wednesday, March 31.

Lecture : 12.2, 18.3 (new edition : 19.2, 25.3)

Lektion : suggested exercises 4.4.2, 4.5.1, 4.5.4, 12.1.3, 12.2.3 (new edition : 11.4.2, 11.5.1, 11.5.4, 19.1.3, 19.2.3)

DAY 5 : Wednesday, April 14

Lecture : 18.3 - 18.6 (new edition : 25.3 - 25.6).

Lektion : 18.3.4, 18.4.1 (new edition : 25.3.4, 25.4.1).

DAY 6 : Monday, April 19.

Lecture : We finished Chapter 18. Extra : Generalised Binomial Theorem and Catalan numbers (only started the latter) - see lecture notes for Day 7.

DAY 7 : Wednesday, April 21.

Lecture : Catalan numbers (continued) and 5.1. ps pdf dvi tex

Lektion : 18.6.1, 5.1.2 (new edition 25.6.1, 12.1.2), plus an extra exercise on Catalan numbers ps pdf dvi tex

DAY 8 : Monday, April 26.

Lecture : 8.1-8.4. Extra : Dirac's theorem on Hamilton cycles. ps pdf dvi tex

DAY 9 : Wednesday, April 28.

Lecture : 8.6, 8.7. Extra : Some remarks on planar graphs. ps pdf dvi tex

Lektion : 8.1.2, 8.2.1, 8.3.1, 8.4.3, 8.6.2, 8.7.1, 8.7.2 (new edition : 15.1.2, 15.2.1, 15.3.1, 15.4.3, 15.6.2, 15.7.1, 15.7.2)

DAY 10 : Monday, May 3.

Lecture : Extra : Some remarks on planar graphs. ps pdf dvi tex Mantel/Turan theorem ps pdf dvi tex

DAY 11 : Wednesday, May 5.

Lecture : 8.5. Some extra stuff on counting trees. ps pdf dvi tex

Lektion : 8.5.1, 9.1.4, 9.1.6 (new edition : 15.5.1, 16.1.4, 16.1.6)

DAY 12 : Monday, May 10.

Lecture : 9.3, 9.4, 9.5, 9.6, 11.1 (started)

DAY 13 : Wednesday, May 12.

Lecture : 11.1-11.5, 10.4 (started) (new edition : 18.1-18.5, 17.4)

Lektion : 9.3.3, 9.4.3, 9.6.1, 11.1.2, 11.5.2 (new edition : 16.3.3, 16.4.3, 16.6.1, 17.1.2, 17.5.2)

DAY 14 : Monday, May 17.

Lecture : 10.4, 10.5.

DAY 15 : Wednesday, May 19

Lecture : 10.5 (ctd.), Extra : König's theorem and connection to MFMC theorem ps pdf dvi tex

Lektion : 10.4.1, 10.4.2, 10.5.3, 10.7.2, 10.7.13 (new edition : 17.5.3, 17.7.2, 17.7.13)

DAY 16 : Monday, May 24.

Lecture : 10.2.

DAY 17 : Wednesday, May 26.

Lektion : 10.2.1, 10.2.3, 10.2.5, 10.7.17 (new edition : 17.2.1, 17.2.3, 17.2.5, 17.7.17).

Lecture : repitition (se ovningstentan and gamla tentor below).

DAY 18 : Wednesday, June 2.

Lecture : repitition.

Lektion : repitition.

For some further exercises on enumerative combinatorics, check out Hemuppgift 1 at the following link

Homework 1 (deadline 17:00 on Wednesday April 21) ps pdf and solutions ps pdf

Homework 2 (deadline 17:00 on Wednesday, May 5) ps pdf and solutions

Homework 3 (deadline 17:00 on Monday, May 24) ps pdf and solutions ps pdf

List of required theorems ps pdf dvi tex

Tentamen 040604 ps pdf dvi tex och losningar ps pdf dvi tex

Övningstenta ps pdf dvi tex

Tentamen 040603 ps pdf dvi tex och lösningar ps pdf dvi tex

Tentamen 230803 ps pdf dvi tex och lösningar ps pdf dvi tex

Tentamen 040602 ps pdf dvi tex och lösningar ps pdf dvi tex

Tentamen 240802 ps pdf dvi tex och lösningar ps pdf dvi tex

A useful website

Some cool 3-D graphs : dodecahedron icosahedron football