Discrete Mathematics Cheat Sheet 6o1u14

Definitions The function is surjective (onto) if every element of the codomain is mapped to by at least one element of the domain. The function is injective (one-to-one) if every element of the codomain is mapped to by at most one element of the domain. The function is bijective if every element of the codomain is mapped to by exactly one element of the domain. Properties of relations: 1. reflexive: for all x in X it holds that xRx (Show that ( x , x ) ∈ R ) 2. symmetric: for all x and y in X it holds that if xRy then yRx. (Show that if ( x , y ) ∈ R , then ( y ,x)∈R ) 3. antisymmetric: for all x and y in X, if xRy and yRx then x = y. (Show that if ( x , y ) ∈ R and ( y , x ) ∈ R , then x = y) 4. transitive: for all x, y and z in X it holds that if xRy and yRz then xRz. (Show that if ( x , y ) ∈ R and ( y , z ) ∈ R , then ( x , z ) ∈ R ) Partial orders are reflexive, antisymmetric, and transitive Equivalence relations are reflexive, symmetric and transitive To write a matrix for a relation R from X to Y, use the elements in X to label the rows and the elements of Y to label the columns Permutations: Order matters The number of ways of obtaining an ordered subset of k elements from a set of n elements is given by ( n !) n Pk = ( n−k ) ! Generalized permutations: n! P ( n ;n1, n2, ... , nk )= n1 ! n2 ! ... n k ! Combinations: Order does not matter The number of ways of picking k unordered outcomes from n possibilities. Also known as the binomial coefficient or choice number and read "n choose k," n! n= n Ck = k ( n−k ) ! k ! Generalized combinations: n+ k−1 = ( n+ k−1 ) ! n Ck = k ( n−1 ) ! k ! k groups from n objects. Binomial Coefficients: We can find these using Pascal's Triangle: n! n= n Cr = r ( n−r ) ! r !

()

(

)

()

where n is the row number and r is an element in that row. Pascal's rule, which says that if

then

for any non-negative integer n and any integer k between 0 and n. If A has n elements, and B has m elements: 

The total number of relations between the two is 2mn



The total number of one-to-one functions is mPn.



The total number of onto functions is nPm.



The total number of bijections is n!

If A has n elements n



There are 2( 2) +n symmetric relations



There are 2n × 3(2 ) antisymmetric relations



There are 2n −n reflexive relations



There are 2( 2) relations that are both reflexive and transitive

n

2

n

Recurrence Relations Order 1:

+ b (the most general solution is an = krn with a0 = k)

Solution: 

If r = 1: an =a0 +nb



n If r ≠ 1: an =r a0 +

[

]

b b − r−1 r −1

Order 2: Solution:



Let an = rn and substitute for all a to get

.



Dividing through by rn−2 to get



Now we solve this polynomial using the quadratic equation



Solve for r to obtain the two roots λ1, λ2

which is the same as

(

A±√ A +4 B 2 2

r=

)

o If they are distinct, then we get o If they are the same, then we get 

Now apply initial conditions Graph Theory

Types of Graphs  Simple graph: No loops or parallel edges  Complete Graph: each pair of vertices has an edge connecting them. n ( n−1 ) ◦ K n has n vertices and edges 2  Bipartite Graph: vertex set can be partitioned into two sets, W and X, so that no two vertices in W are adjacent and no two vertices in X are adjacent ◦ Cannot contain an odd cycle  Complete Bipartite Graph: ◦ If m=|W | and n=|X| , then: K m , n has m + n vertices and nm edges ▪  Planar Graph: can be drawn in such a way that no edges cross each other ◦ Kuratowski's Theorem: A finite graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 or K3,3. ◦ Euler's formula: v − e + f = 2. ◦ Graph is not planar if it contains a subgraph homeomorphic to K3,3 or K5 Types of Cycles:  A cycle is a path that starts and ends at the same vertex and does not repeat edges  Euler Cycle: Every vertex in the graph must have even degree. Traverses every edge exactly once.  Hamiltonian Cycle: Visits each vertex exactly once.  Simple Cycle: closed walk with no repetitions of vertices and edges allowed, other than the repetition of the starting and ending vertex Isomorphism: 

Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic.