HOME SCHEDULE EXERCISES ASSIGNMENTS BOOK ZOOM FIRE TIME-EDIT
SCHEDULE EXERCISES ASSIGNMENTS BOOK ZOOM FIRE TIME-EDIT

Lecture Notes on Combinatorics

Read: Lehman, Leighton, and Meyer: Chapter 15.

Notes on Combinatorics (swedish, pdf).

Haskell code implementing some of these methods. You can look at the code to understand the methods, and also run it on examples.

Lecture Notes:

Basic combinatorics

Addition principle: Combining exclusive choices using +. Example: Lunch at restaurant 1 has 20 choices, lunch at restaurant 2 has 3 choices; total: 23 choices.

Multiplication principle: Combining simultaneous, independent choices using *. Example: Lunch has 3 choices, ice cream has 10 choices; total number of different lunches is 30.

Subtraction principle: Taking away choices you want to exclude using -. Example: I don't like eat mango for lunch AND dessert. One lunch with mango chutney, 2 ice creams with mango; total number of lunches is 30-2=28.

Division principle: When you have counted choices you regard as the same as different choices, divide by the size of the group. Example: 20.19 pizza pairs, but the order does not matter, so really 20.19/2 combinations.

We saw a combinatorial proof: Count the same thing in two different ways, and show that they are equivalent.

Basic probability

Let T the number of Total outcomes (all equally likely).

Let G be the number of Good outcomes.

Probability that a Good thing happens: G/T.

Alternatively, let B be the number of Bad outcomes. Probability that a Good thing happens: (T-B)/T.

We looked at the birthday problem: What is the probability that two students in the class have their birthday on the same day?

Permutations, combinations

Permutations: n!, or n!/(n-k)! if we choose k things from n things and order them.

Combinations: \({n \choose k}\) if we choose k things from n things and we do not care how they are ordered. These are also called binomial coefficients.

Pascal's triangle. The sum of all binomial coefficients for n is \(2^n\).

Using Pascal's triangle, we also saw that: \[ { n \choose k } + { n \choose k+1 } = { n+1 \choose k+1 } \]

Pigeon hole principle (lådprincipen)

If n+1 pigeons fly into n holes, at least one hole must have at least 2 pigeons in it.

Alternatively: "the maximum is always greater than or equal to the average". The average number of pigeons per hole is (n+1)/n, which is greater than 1. The maximum number of pigeons per hole (which must be a natural number) is therefore at least 2.