Discrete Mathematics Answers

How many permutations of the 26 letters of our alphabet do not contain any of the three strings "US", "AIM", and "DONKEY"?

Let X be a non-empty set, and let R be an equivalence relation on X. Let C be the set of all equivalence classes of R. So C={A⊆X such that A=[x] for some x ∈ X}.

Now, define f : X → C by the rule f(x) = [x] for all x ∈ X.

Prove that if x ∈ X, then there is one and only one equivalence class which contains x.

Suppose X = {1, 2, 3, 4, 5} and that R is an equivalence relation for which 1 R 3, 2 R 4 but 1 R̸ 2,1 R̸ 5,and 2 R̸ 5.

Write down the equivalence classes of R and draw a diagram to represent the function f.

Let X = {1,2,3}. Define a relation ∼ on P(X) by A ∼ B if A and B have the same number of elements.

Prove that ∼ is an equivalence relation and write down all equivalence classes of ∼.

Let X be a non-empty set, and let R be an equivalence relation on X. Let C be the set of all equivalence classes of R. So C={A⊆X such that A=[x] for some x ∈ X}.

Now, define f : X → C by the rule f(x) = [x] for all x ∈ X.

Suppose X = {1, 2, 3, 4, 5} and that R is an equivalence relation for which 1 R 3, 2 R 4 but 1 R̸ 2,1 R̸ 5,and 2 R̸ 5.

Write down the equivalence classes of R and draw a diagram to represent the function f.

Let X be a non-empty set, and let R be an equivalence relation on X. Let C be the set of all equivalence classes of R. So C={A⊆X such that A=[x] for some x ∈ X}.

Now, define f : X → C by the rule f(x) = [x] for all x ∈ X.

Prove that if x ∈ X, then there is one and only one equivalence class
which contains x.

Let X = {1,2,3}. Define a relation ∼ on P(X) by A ∼ B if A and B have the same number of elements.

Prove that ∼ is an equivalence relation. Write down all equivalence classes of ∼.

3. Prove or give a counterexample to the following: For a set A and
binary relation R on A, if R is reflexive and symmetric, then R must
be transitive as well.

DISCRETE STRUCTURES

1. Prove the following formulas for all positive integers n.
a) 1 + 2 + 3 + 4 + 5 +...+ n = n(n + 1) :2
b) 1 + 4 + 9 + 16 + 25 + ...+ n2 = n(n + 1)(2n + 1) :6
c) 22n - 1 is a multiple of 3

Find domain and range of (answers should be subsets of R):

f(x)= x/(x^2+1)

Find domain and range of (answers should be subsets of R):

f(x)= 1/(5x-6)