Discrete Mathematics Lecture Notes

Flashcards covering key vocabulary and concepts from the discrete mathematics lecture notes.

Catalan Numbers

A sequence of natural numbers that occurs in various counting problems including counting the number of correct ways to parenthesize expressions, the number of paths through a grid, etc.

Fibonacci Numbers

A sequence where each number is the sum of the two preceding ones, commonly used in counting problems.

n-second Walk

A sequence of steps where each step is either up (U) or down (D), starting and ending at the same level.

Recurrence Relation

An equation that recursively defines a sequence: a relation between term and terms that have come before it.

Injective Function

A function where different inputs map to different outputs.

Surjective Function

A function where every element in the codomain is an output of some element from the domain.

Bijective Function

A function that is both injective and surjective, establishing a one-to-one correspondence between elements of the domain and codomain.

Pigeonhole Principle

A principle stating that if n items are put into m containers with n > m, then at least one container must contain more than one item.

Union of Sets

The set containing all elements from the given sets, denoted as A ∪ B.

Intersection of Sets

The set containing all elements that are common to both sets, denoted as A ∩ B.

Power Set

The set of all subsets of a given set, including the empty set and the set itself.

Cartesian Product

The set of all ordered pairs formed by taking one element from each of two sets.

Cardinality

A measure of the 'number of elements' in a set.