math 61 midterm 2 definitions discrete math

addition principle

If there are two pairwise disjoint sets, the total number of elements in either set is the sum of the number of elements in each set.

bit string

A sequence of bits, typically represented as a string of binary digits (0s and 1s), that can encode data or information.

inclusion exclusion principle

A method for calculating the size of the union of multiple sets by using the sizes of the individual sets and their pairwise and higher-order intersections.

permutation (no repetition)

An arrangement of objects in a specific order, where no object is used more than once in each arrangement.

permutation (with repetition)

A way of arranging items where some items can be repeated, allowing for a larger set of arrangements than if all items were unique.

combination (no repetition)

A selection of items from a larger set, where the order of selection does not matter and each item can only be chosen once.

combination (with repetition)

A selection of items from a larger set where each item can be chosen more than once, and the order of selection does not matter.

binomial theorem

A mathematical formula that provides a way to expand expressions raised to a power, denoted as (a + b)^n, where the coefficients are given by binomial coefficients.

Pascal’s triangle

A triangular array of binomial coefficients, where each number is the sum of the two directly above it, used to expand binomial expressions.

pigeonhole principle

A concept in combinatorics stating that if n items are put into m containers, with n > m, then at least one container must contain more than one item. Alternatively, nk + 1 pigeons, n holes such that nk + 1 >= n + 1 is satisfied, guarantees at least one hole contains at least k + 1 pigeons.

generalized pigeonhole principle

An extension of the principle that states if n items are distributed among m containers, at least one container must hold at least (\lceil n/m \rceil) items.

r-combination

A selection of r elements from a set of n elements, without regard to the order of selection. The number of r-combinations is calculated using the formula n! / (r!(n-r)!).

grid walk

A path on a grid that consists of a sequence of steps in specified directions, typically moving right or up in a coordinate system, often used in combinatorial problems. Typically encompasses moves in defined directions such as right and up, thereby forming a path on a two-dimensional grid, commonly analyzed in combinatorial mathematics.

stars and bars

A combinatorial method used to determine the number of ways to put n indistinguishable objects into k distinguishable boxes, allowing for empty boxes. (Stars + bars) choose (bars).

recurrence relation

A mathematical equation that defines a sequence recursively by relating each term to one or more of its predecessors. Recurrence relations are widely used to solve problems in algorithm analysis and combinatorial mathematics.

Fibonacci sequence

A sequence where each number is the sum of the two preceding ones, starting from 0 and 1. It is often represented as F(n) = F(n-1) + F(n-2) for n > 1. Defined by the recurrence relation where F(0) = 0, F(1) = 1, and for n ≥ 2, F(n) = F(n-1) + F(n-2). This sequence appears in various fields, including mathematics, computer science, and nature.

recursive definition

A method of defining a function or sequence in terms of itself, typically specifying base cases and recursive cases to generate the entire set of values.

closed formula

A mathematical expression that provides a direct computation for the nth term of a sequence, without requiring recursion. It allows for quick evaluation of terms, often derived from the analysis of a recurrence relation.

linear homogeneous recurrence relations with linear coefficients

A type of recurrence relation in which each term is a linear combination of previous terms, with constant coefficients, and the sequence is defined by homogeneous conditions such that there are no additional constants or terms present.

linear inhomogeneous recurrence relations with constant coefficients

A recurrence relation where each term is a linear combination of previous terms with constant coefficients, plus a non-homogeneous term, allowing for additional specific values or functions to influence the sequence. This type of recurrence relation includes both the linear combination of previous terms with constant coefficients and an additional function or constant that influences the sequence.

graph

A collection of vertices connected by edges, used to represent relationships or connections within data structures in discrete mathematics.

adjacent

Two vertices are this if they are connected by an edge in a graph.

incident

Two edges are this if they share a common vertex in a graph.

degree of vertex

number of edges incident to a given vertex

complete graph

denoted as Kn, has an edge between every vertex

bipartite graph

a graph if considered this if there is a partitioning of V, {V1, V2} such that every edge in E is incident to an element in V1 and V2 each.

complete bipartite graph

denoted Km,n, a bipartite graph where {V1, V2} is a partition of V with |V1| = m, |V2| = n, and there is an edge between every element in V1 and V2

cycle graph

on n >= 3 vertices is graph, Cn, with vertices V = {V1, . . . , Vn} → E = {{V1, V2}, {V2, V3}, . . . , {Vn-1, Vn}, {Vn, V1}}

paths graph

denoted Pn, n vertices → V = {V1, . . . , Vn}, E = {{V1, V2}, . . . , {Vn-1, Vn}}

path of (length n)

let G(V, E) be a graph where n = 0, 1, . . . , n. A finite sequence of vertices {V0, . . . , Vn} such that Vi is adjacent to Vi+1 for every i = 1, 2, . . . n - 1.

connected

let G be a graph. Vertices x and y are this if there exists a path form x to y in G (every vertex is connected by itself) A graph is this if every x, y in V is connected

subgraph

G(V, E) is a graph. A graph G’ = (V’, E’) is this if V’ and E’ are subsets of V and E, respectively, and if {x, y} are in E’, x, y are in V’.

simple path

G(V, E) is a graph and x, y are in V. A path from x to y is this if no repeated vertices

cycle

G(V, E) is a graph and x is in V. At x, is a path from x to x with no repeated edges

simple cycle

A cycle with no repeated vertices

closed path

A path that simply starts and stops on the same vertex

Eularian cycle

cycle that visits all vertices and contains all edges

finite graph

V is finite for G(V, E)

Hamiltonian cycle

a cycle that visits all vertices exactly once, except the starting vertex (has a cycle length equivalent to number of edges)

degree sequence

a list of the degrees of all the vertices of a graph in descending order