Chapter 4:

- A sequence is an usually infinite ordered list of elements.

- String: given a set X, a string over X is a finite ordered list of elements of X.

- Principle of mathematical induction: let P be a property of positve intergers such that:

o 1. Basic step: P(1) is true and

o 2. Inductive step: if P(n) is true then P(n+1) is true

Then P(n) is true for all positive intergers.

- Strong form of mathematical induction: let P be a property of positve intergers such that:

o 1. Basic step: P(1) is true and

o 2. Inductive step: if P(k) is true for all 1<= k <= n then P(n+1) is true

- Then P(n) is true for all positive intergers

- First order recurrence relations:

- Second order recurrence relations:

Chapter 5

- The rule of sum: if A and B are disjoint, then:

|A Ü B| = |A| + |B|

More generally, if the set A1, A2, ..,An are paiwise disjoint then:

|A1 Ü A2 Ü ... Ü An| = |A1| + |A2| + ... + |An|

- The rule of product: if A and B are disjoint, then:

|A ∩ B| = |A| . |B|

More generally, if the set A1, A2, ..,An are paiwise disjoint then:

|A1 ∩ A2 ∩ ... ∩ An| = |A1| . |A2| . ... . |An|

- The Inclusion-Exclusion principle: generalize the rule of sum to non-disjoint sets

For arbitraty but finite sets A, B: |AÜB| = |A| + |B| - |A∩B|

- Permutations: assume we have n objects. Any arrangement of any k of these objects in a given order is call a permutation of size k.

The number P(n,k) pf permutations of size k of n given objects is:

P(n,k) = n!/(n-k)!

- Combinations: assume we have a set A with n objects. Any subset of A of size r is called a combination of n elemnts taken r at a time.

C(n,r) = n!/r!(n-r)! = P(n,r)/P(r,r)

- Permutations with repeated elements: assume that we have an alphabet with k letters and we want to write all possible workd containing n1 times the 1st letter, n2 times the 2nd letter, .. nk times the kth letter. How many words we can write? We call this number P(n; n1, n2, ...,nk) where n=n1+n2+..+nk

P(n; n1, n2, ...,nk) = n!/n1!n2!...nk!

- Combinations with repetition: assume that we have a set A with n element. Any selection if r objects from A,where each object can ve selected more than once, is call a combination of n obkjects taken r at a time with repetition.

- The pigeonhole principle: If n pigeonholes are occupied by m pigeons and m > n then at least one pigeonhole is occupied by more than one pigeon.

Chapter 6:

- Probalility function: the probability of each possible outcome x is a function P(x). This function verifies: 0 <= P(x) <= 1 for all x ε S

And ΣP(x) = 1, x ε S

- Properties of probability"

o For every event E belongs to S: 0 <= P(E <= 1

o P(0) = 0; P(S) =1

o For every E belongs to S if !E is the complement of E then P(!E) = 1 - P(E)

o If E1, E2 are two event the

P(E1ÜE2) = P(E1) + P(E2) - P(E1∩E2)

- Conditional probability: the conditional probability of an event E given F, represented P (E|F) is the probaiblity of E assuming that F has occurred.

P(E|F) = P(E∩F)/P(F)

Independent events: two events E F are said to ve independent of the probability of one of them does not depend on the other:

P(E∩F) = P(E).P(F)

- Bayers' theorem:

P(F) = Σ P(F|Ci).P(Ci)

P(Cj|F) = P(F|Cj).P(Cj)/P(F)