Discrete mathematics

MATH-260(a)

Media

MATH-260 Discrete Mathematics

Random variables and their expectations

30.05.2021, 11:11

Probabilistic method and its applications

30.05.2021, 11:03

Finite probability spaces

28.05.2021, 17:10

Binet-Cauchy theorem

22.05.2021, 10:43

Matrix tree theorem

14.05.2021, 19:57

Graphs and matrices

14.05.2021, 19:54

Minimal spanning tree

09.05.2021, 15:53

Subgraphs vs induced subgraphs

09.05.2021, 15:50

Estimating the number of unlabeled trees

01.05.2021, 23:24

Counting labeled trees

01.05.2021, 23:23

Graph isomorphisms

01.05.2021, 23:22

Basics of graph theory

23.04.2021, 23:26

Möbius inversion for posets

18.04.2021, 00:04

Counting cyclic sequences

17.04.2021, 00:14

Möbius inversion formula

16.04.2021, 23:38

Linear recurrence relations

27.03.2021, 15:58

Fibonacci numbers and the golden ratio

26.03.2021, 23:40

More about Catalan numbers

20.03.2021, 14:32

Binary trees and Catalan numbers

20.03.2021, 00:13

Computations with power series

12.03.2021, 23:14

Combinatorial applications of polynomials

12.03.2021, 22:59

Proofs by induction

06.03.2021, 00:45

We review the induction principle and the structure of proofs by induction.

Inclusion-Exclusion formula

05.03.2021, 22:53

We prove the inclusion-exclusion formula and use it in two applications. Namely, we compute the number of permutations without fixed points and the  Euler's totient function.

Binomial coefficients and the bell curve

28.02.2021, 22:46

Birthday paradox

26.02.2021, 22:58

In this video we discuss whether coincidences are surprising or not. 

Binomial coefficients

21.02.2021, 10:12

Basics of counting

20.02.2021, 22:38

In this video we explain the main rules of counting for combinatorial objects and relate them to basic results of set theory.


Media

MATH-260 Discrete Mathematics

Random variables and their expectations

30.05.2021, 11:11

Probabilistic method and its applications

30.05.2021, 11:03

Finite probability spaces

28.05.2021, 17:10

Binet-Cauchy theorem

22.05.2021, 10:43

Matrix tree theorem

14.05.2021, 19:57

Graphs and matrices

14.05.2021, 19:54

Minimal spanning tree

09.05.2021, 15:53

Subgraphs vs induced subgraphs

09.05.2021, 15:50

Estimating the number of unlabeled trees

01.05.2021, 23:24

Counting labeled trees

01.05.2021, 23:23

Graph isomorphisms

01.05.2021, 23:22

Basics of graph theory

23.04.2021, 23:26

Möbius inversion for posets

18.04.2021, 00:04

Counting cyclic sequences

17.04.2021, 00:14

Möbius inversion formula

16.04.2021, 23:38

Linear recurrence relations

27.03.2021, 15:58

Fibonacci numbers and the golden ratio

26.03.2021, 23:40

More about Catalan numbers

20.03.2021, 14:32

Binary trees and Catalan numbers

20.03.2021, 00:13

Computations with power series

12.03.2021, 23:14

Combinatorial applications of polynomials

12.03.2021, 22:59

Proofs by induction

06.03.2021, 00:45

We review the induction principle and the structure of proofs by induction.

Inclusion-Exclusion formula

05.03.2021, 22:53

We prove the inclusion-exclusion formula and use it in two applications. Namely, we compute the number of permutations without fixed points and the  Euler's totient function.

Binomial coefficients and the bell curve

28.02.2021, 22:46

Birthday paradox

26.02.2021, 22:58

In this video we discuss whether coincidences are surprising or not. 

Binomial coefficients

21.02.2021, 10:12

Basics of counting

20.02.2021, 22:38

In this video we explain the main rules of counting for combinatorial objects and relate them to basic results of set theory.


This file is part of the content downloaded from Discrete mathematics.

Welcome to discrete mathematics!

In this course we will learn the following topics:

  1. Elementary combinatorics, counting.
  2. Graphs, trees.
  3. Partially ordered sets, set systems.
  4. Generating functions.
  5. Probabilistic method.
  6. Linear Algebra method.


Exam

60% of the final grade are awarded for the written final exam and 40% of the grade come from the homework done during the semester.

Homework

One homework exercise has to be submitted each week. Late submissions are not excepted. The final grade for the homework is calculated as the average of the 10 best weekly grades of a student. Work in groups up to 3 people is allowed, however a student has to understand the solution and give  the credit for collaborative work. While group members can collaborate on understanding and solving problems, each person must submit their own uniquely written document.


Lectures

Live lectures Mondays at 8:15 in the room CM 1 and video lectures on Switchtube .

Exercises

Exercise sessions on Tuesdays at 8:15 in the rooms CE1103, CE1106.

Important announcements

The final Q&A session will take place on June 23rd from 11:00 till 12:00 in the lecture hall CM 1 120.



Topics: 

  • Counting problems
  • Number of subsets
  • Pascal's triangle
  • Binomial theorem
  • Permutations

To watch:

To read:
[Lov] 1.2. Sets, 1.3. Number of subsets, 1.5. Sequences, 1.6. Permutations, 1.7. Number of The Number of Ordered Subsets, 1.8. The Number of Subsets of a Given Size, 3.1.
The Binomial Theorem, 3.2. Distributing Presents, 3.5. Pascal’s Triangle, 3.6. Identities in Pascal’s Triangle.
[Mat] Chapters 3.1-3.3.


Topics:

  • O, o-notation
  • Stirling theorem
  • Birthday paradox
  • Estimates for binomial coefficients

To read:
[Lov]  2.2.4. Pigeonhole principle.  2.2.5 The Twin Paradox
[Mat] 3.4. Estimates: an introduction - starting from 3.4.2. - Big Oh, little oh, 3.5.5. Estimate n!
- second proof only

To watch:





Topics:

  • Inclusion-exclusion principle
  • Permutations without fixed points
  • Euler's function  \varphi(n)

To read:
[Lov] 2.2.1 Induction, 2.2.3. Inclusion-Exclusion
[Mat]  3.7. Inclusion - Exclusion.

To watch:

Lecture:
  • Generating functions
  • Combinatorial applications of polynomials
  • Calculations with power series

To read:
[Mat] Chapters 12.1, 12.2.



Lecture:
  • Counting binary trees
  • Catalan numbers

To read:
[Mat] 12.4  Binary trees.


In case you became interested in generating functions I suggest this book:

Topics:
  • Fibonacci numbers
  • Linear recurrence relations

To read:
[Mat] 12. 3 Fibonacci numbers and the golden section.
[Lov] 4. Fibonacci Numbers.


Topics:

  • Möbius inversion formula
  • Number of cyclic sequences
  • Partially ordered sets
  • Möbius inversion for posets

To read:
[Hall] Chapters 2.1 and 2.2


Topics:

  • Basic definitions of graph theory
  • Counting labelled trees
  • Counting unlabelled trees

Lecture:

  • Subgraphs and induced subgraphs
  • Weighted graphs. Minimal spanning tree
  • Kruskal's algorithm for finding a minimal spanning tree
  • Adjacency matrix, incidence matrix , and laplacian matrix of a graph

To read:
[Lov] 9.1 Finding the Best Tree
[Mat] 4.2 Subgraphs, components, adjacency matrix. 5.4. Minimum  spanning tree problem.



To read:
[Mat] 8.5 Proofs working with determinants




Topics:
  • Finite probability spaces
  • probabilistic method
  • random graphs
To read :
[Mat] Chapter 10. Probability and probabilistic proofs
[Lov] Chapter 5. Section 5.1 Events and probabilities
On random graphs (1959) (This topic will not be covered in the exam)

To watch:



Probabilistic method

  • Ramsey numbers. Slides
  • Hamiltonian paths a tournament (optional home reading in the lecture notes)

  • Erdős-Ko-Rado theorem. Slides

To read:
Sections 2.1, 2.3 and 3.2 of this lecture notes by Jiří Matoušek Jan Vondrák




Mock Exam Week.

Some notes about the Mock Exam:

- The number of questions in the final exam may be different than in the mock exam, but not very different.
- The questions did mostly appear in the actual exam in 2023.


Discussion Session and Review Week


Exam viewing