CMPE 201 • Final • Discrete Computational Structures

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 2

Example 3

Pascal Identity

Combinatorial Proof

Example 4

Pigeonhole Principle

Example 1

Example 2

Example 3

Example 4

Example 5

Counting 1

Counting 2

Counting 3

Counting 4

Counting 5

Counting 6

Counting and Binomial Coefficients

Binomial Coefficient and Identities 1

Binomial Coefficients and Identities 2

Pigeonhole Principle 1

Pigeonhole Principle 2

Pigeonhole Principle 3

Pigeonhole Principle 4

Pigeonhole Principle 5

Pigeonhole Principle 6

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

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

Introduction

Rooted Tree

Terminology for Rooted Trees

Full m-ary Trees

Some Formulas

Recurrence Relations 1

Recurrence Relations 2

Recurrence Relations 3

Recurrence Relations 4

Recurrence Relations 5

Recurrence Relations 6

Recurrence Relations 7

Recurrence Relations 8

Recurrence Relations 9