mh-logo
   

MAAA98 Diskret Matematik A för CV1
Week 19


Functions and Combinatorics

We continue our discussions about functions this week by considering invertible discrete functions, and we shall also discuss the magnitude of functions and basic complexity theory.

In the combinatorics section we will be concerned with answering 'how many'-type questions. We have met the fundamental principles for answering this type of question earlier in the course: The Multiplication Principle and the Addition Principle.

Recall that we looked at the size of the set AxB, that is the cartesian product of A and B (it consists of pairs (a,b) where a in A and b in B.) We saw that the cardinality |AxB| = |A| |B|. This is the Multiplication Principle for two sets.

Lecture 12

References: [CD] 3.7 - 3.9, and the online note [CT]
Exercises: [CD] 3.9.1, 3.9.2, 3.9.4, 3.9.7, 3.9.9.

([CT] refers to Notes on Complexity Theory (available online now))
 

Lecture 13

References: [CD] 4.1 - 4.3.
Exercises: [CD] 4.2.1, 4.2.2, 4.2.5, 4.2.7, 4.2.8, 4.2.10, 4.3.1, 4.3.2, 4.3.3, 4.3.5, 4.3.6
 

Lecture 14

References: [CD] 4.3 - 4.6.
Exercises: [CD] 4.3.8, 4.3.10, 4.3.13, 4.4.4, 4.6.1, 4.6.2, 4.6.3, 4.6.4.

Övning 3 (Wednesday 10-12)

You will have time to finish the group assignment which we started in week 14. The presentations are scheduled for Friday. Your reports should be in by Friday 19 May at 8am.

Presentations (Friday 10-12, 13-15)

Presentation of your Group Assignment.
If there is time left over, I will continue my lectures on combinatorics.
 


Inlämningsuppgift 5

Click here for an English version.

För att få bonuspoängen måste du lämna in ett bra försök på alla frågorna innan
onsdagen den 17 maj, kl 8:00.

  1. En gitterpunkt i tre dimensionella rymden är en punkt som har heltalskoordinater. Antag att det finns nio gitterpunkter, och en linje mellan varje par.
    1. Bestäm antalet linjer.
    2. Bestäm formel för mittpunkten av linjen mellan två punkter.
    3. Visa att mittpunkten av en av linjerna också är en gitter punkt.
  2. Vilka av följande funktioner är injektioner, surjektioner eller bijektioner? Visa dina svar!
    1. f: integers to integers där f(n)=7n+3.
    2. g: positive integers to positive integers där g(n)=n+7.
    3. h: integers to integers där h(n)=n+7.
Pia Heidtmann
© MITTUNIVERSITETET
Institutionen för Teknik, Fysik och Matematik
Mitthögskolan
SE-851 70 SUNDSVALL
Sweden