Discrete Mathematics Answers

Write down all derangements of the set \left\{ a,b,c,d \right\} and show that the number of derangements is the same as predicted by the recurrence D(n) = (n - 1)(D(n - 2) + D(n - 1)) with initial values D(1) = 0 and D(2) = 1. Hint: a derangement is a permutation of an ordered set where no element is in the same place as before. Example: \left\{ b,a,d,c \right\} is a derangement of \left\{ a,b,c,d \right\} because all of the letters positions have changed.

Consider a relation R on a set A = { 2, 4, 7 }.

Given the relation R = { (2, 2), (2, 4), (2, 7), (4, 7}. Find:

1. Complement of a Relation

_____________________________________________________

_____________________________________________________

2. Inverse of a Relation

__________________________________________________________________________________________________________

3. Composite Product R o S and S o R ; S = { (1, 2), (2, 4), (2, 7) }

If 1 + 2 = 3, then 3 is odd.

There is a set X = {1, 2, 3, 4, 5}. Find the sets A, B, C such that A ⊆ X, B ⊆ X,

C ⊆ X,

(A ∪ B) ⊆ (A ∩ C)

and C 6⊆ B.

1. Let A = { 2, 3 }, and B = { 3, 4, 5, 6 }

Let R be a relation from A to B where

R = {(x, y) “x exactly divides y”}

Enumerate the following:

A. elements of R; R = { ______, ______, ______, ______ }

rewrite R as a table.

A B

2. Let R be a relation on A = { 1, 2, 3 } defined by

R = { (x, y) l x ≤ y ˄ x, y ∈ A }

Identify the domain and range of the relation R.

Solve the recurrence relation A(n) = 6A(n - 1) - 11A(n - 2) + 6A(n - 3) subject to initial values A(1) = 2, A(2) = 6, A(3) = 20.

2. Use set builder notation to give a description of each of

these sets.

a) {0, 3, 6, 9, 12}

b) {−3, −2, −1, 0, 1, 2, 3}

c) {m, n, o, p}