D421 Discrete Math: Functions and Relations - Set 3 - Part 1

Correct Answer: The product of all positive integers from 1 to n

n! is the product 1 × 2 × 3 × ... × n. For example, 4! = 24. By convention 0! = 1.

Correct Answer: Ordered arrangements of objects

A permutation counts arrangements where order matters, so ABC and ACB are different permutations.

Correct Answer: Selections where order does not matter

A combination counts selections without regard to order, so choosing {A, B, C} is the same regardless of arrangement.

Correct Answer: 24

The number of arrangements of 4 distinct objects is 4! = 4 × 3 × 2 × 1 = 24.

Correct Answer: 10

The number of combinations C(5,3) = 5! / (3! × 2!) = 120 / 12 = 10.

Correct Answer: n! / (n − r)!

P(n, r) = n! / (n − r)! counts ordered arrangements of r objects chosen from n.

Correct Answer: n! / (r!(n − r)!)

C(n, r) = n! / (r!(n − r)!) counts unordered selections of r objects from n.

Correct Answer: 15

C(6, 2) = 6! / (2! × 4!) = 720 / (2 × 24) = 15.

Correct Answer: If one task has m outcomes and another n, together they have m × n outcomes

The product rule states that independent successive choices multiply: m ways for the first and n for the second give m × n total outcomes.

Correct Answer: If tasks are mutually exclusive with m and n ways, there are m + n ways total

The sum rule states that if two choices cannot both be made, the number of options is the sum m + n.

Correct Answer: A graph whose edges have a direction

A directed graph has edges with a direction, represented as ordered pairs of vertices, indicating a one-way relationship.

Correct Answer: The number of edges incident to it

The degree of a vertex is the number of edges connected to it, with a loop counting twice.

Correct Answer: It equals twice the number of edges

The sum of all vertex degrees equals twice the number of edges, since each edge contributes to the degree of two vertices.

Correct Answer: A sequence of vertices connected by edges without repeating vertices

A path is a sequence of distinct vertices where consecutive vertices are joined by edges.

Correct Answer: A path that begins and ends at the same vertex

A cycle is a closed path that returns to its starting vertex without otherwise repeating vertices.

Correct Answer: A graph in which there is a path between every pair of vertices

A graph is connected if every pair of vertices is joined by some path.

Correct Answer: A connected graph with no cycles

A tree is a connected, acyclic graph. A tree with n vertices has exactly n − 1 edges.

Correct Answer: n − 1

Every tree with n vertices has exactly n − 1 edges, one fewer than the number of vertices.

Correct Answer: A graph where every pair of vertices is connected by an edge

In a complete graph K_n, every distinct pair of vertices is joined by an edge, giving C(n, 2) edges.

Correct Answer: A graph whose vertices split into two sets with edges only between the sets

A bipartite graph's vertices can be divided into two disjoint sets so that every edge connects a vertex in one set to one in the other.