CE 215 • Final • Discrete Mathematics for Computer Science

Introduction

Proof of Formulas by Induction

Example 1

Example 2

Proof of Divisibility by Induction

Example 1

Example 2

Proof of Inequality by Induction

Example

Induction Related to Fibonacci

Strong Induction

Example 1

Basic Principles of Counting

Counting Examples

Permutations

Permutations Example

Groups and Circular Permutation Example

Identical Objects Example 1

Identical Objects Example 2

Identical Objects Example 3

Combination

n choose r

Committee Example 1

Committee Example 2

Ball Example 1

Ball Example 2

Binomial Theorem

Example 1

Example 3

Example 2

Pascal Identity

Vandermonde's Identity

Example 1

Combinatorial Proof

Example 1

Principle Inclusion-Exclusion

Example 1

Example 2

Pigeonhole Principle

Example 1

Example 2

Example 3

Example 4

Example 5

Example 6

Induction for Formulas 1

Induction for Formulas 2

Induction for Formulas 3

Induction for Formulas 4

Induction Proof for Divisibility 1

Induction Proof for Divisibility 2

Induction for Inequalities

Induction with Fibonacci

Counting 1

Counting 2

Counting 3

Counting 4

Counting 5

Counting 6

Counting 7

Counting & Binomial Coefficients 1

Principle Inclusion - Exclusion

Pigeonhole Principle 1

Pigeonhole Principle 2

Pigeonhole Principle 3

Pigeonhole Principle 4

Pigeonhole Principle 5

Introduction

Homogenous Recurrence Relations

Example 1

Example 2

Example 3

Example 4

Non Homogenous Recurrence Relations

Example5

Example 6

Creating Recurrence Relations

Example 7

Example 8

Example 9

Definition

Example 1

Example 2

Example 3

Example 4

Extended Binomial Theorem

Counting Problems with Generating Functions

Example 5

Example 6

Example 7

Definition of Relation

Example

Example

Example

Example

Reflexive Relations

Example

Example

Symmetric Relations

Antisymmetric Relations

Example

Transitive Relations

Example

Properties of Relations

Example

Example

Example

Composition of Relations

Combining Relations

Inverse and Complementary of a Relation

Equivalence Relation

Example

Example

Example

Recurrence Relations 1

Recurrence Relations 2

Recurrence Relations 3

Recurrence Relations 4

Recurrence Relations 5

Generating Functions 1

Generating Functions 2

Generating Functions 3

Generating Functions 4

Generating Functions 5

Generating Functions 6

Generating Functions 7

Generating Functions 8

Relations 1

Relations 2

Relations 3

Relations 4

Relations 5

Relations 6

Relations 7

Introduction

Graph Terminology

Handshaking Theorem

Example 1

Special Graphs

Example 2

Bipartite Graphs

Example 3

Example 4

Complete Bipartite Graph

Matching

Subgraph

Example 5

Subgraph Induced

Edge Contraction

Example 6

Complementary Graph

Adjacency Matrices - Undirected Graphs

Adjacency Matrices - Directed Graphs

Example 1

Example 2

Incidence Matrices

Example 3

Isomorphism of Graphs

Example 4

Example 5

Example 6

Example 7

Definition of Paths and Circuits

Connected Graphs

Euler Paths and Circuits

Example 8

Hamilton Paths and Circuits

Example 9

Example 10

Planar Graph

Planar Graph - Euler Formula

Example 11

Corollaries about Planar Graph

Example 12

Introduction

Rooted Tree

Terminology for Rooted Trees

Full m-ary Trees

Some Formulas

Handshaking Theorem 1

Handshaking Theorem 2

Handshaking Theorem 3

Adjacency Matrices

Incidence Matrices

Bipartite Graphs & Euler Circuits

Bipartite Graphs, Euler Circuit & Planar Graphs

Euler Path, Induced Subgraph & Incidence Matrix

Chromatic Number 1

Chromatic Number 2

Isomorphism 1

Isomorphism 2

Isomorphism 3

Isomorphism 4

Isomorphism 5

Trees 1

Trees 2

Trees 3

Trees 4

Trees 5

True/False Problems