Discrete Mathematics Answers

Let R be a relation from A to B. Both sets are finite, with |A|=n and |B|=m. Define the complementary relation "R bar" as follows:

R bar={(a, b)|(a,b)∈R}

Calculate |R bar|.

Suppose a friend asks you to list out all relations on the set S = {n|n ∈ Z+ and n≤1000}. Find the number of number of relations on S. Is your friend making a reasonable request?

How many solutions are there to the inequality x1+x2+x3+x4≤15, where x1,x2,x3, and x4 are nonnegative integers?
Hint: Introduce an extra variable x5 and consider x1+x2+x3+x4+x5 = 15.

How many ternary strings (i.e., the only allowable characters are 0, 1, and 2) of length 15 are there containing exactly four 0s, five 1s, and six 2s?

b) Read Section 2.3.6 (on page 161) of the 8'th edition of Rosen's book on partial functions. Let A and B be finite sets, with |A| = m and |B| = n. Calculate the number of partial functions f: A -> B.

(a) We say that two positive integers a, b are relatively prime if the greatest common divisor of a and b is 1. Let p, q be distinct positive prime numbers such that n=pq. Calculate the number of positive integers not exceeding n that are relatively prime to n.

(b) Find a concise, explicit description for the set A, which is defined by 1 ∈ A, and if a and B are bit strings in A, then aB ∈ A, 0aB ∈ A, a0B ∈ A, and aB0 ∈ A.

(a) Define r(n, m) : N x Z+ ->N be the remainder obtained when dividing m into n. Define the function g: Z+ x Z+ ->Z+ as follows: g(a, b) = b if r(a, b) = 0, and g(a, b) = g(b, r(a,b)) otherwise. Describe what g is calculating, and justify your answer.

For all parts of this problem, let S be a finite set, with |S|=n.
(a) If f:S -> S is onto, does it necessarily follow that f is invertible? Why or why not?
(b) Compute the number of distinct functions g:S -> S that are onto.
(c) Find the number of functions f:S -> S that are not invertible.

Define r(n, m) : N x Z+ -> N be the remainder obtained when dividing m into n. Define a function fm: N x N -> N as follows: f(n, k) = k if r(n, m) = 0, and f(n, k) = f(n-m, k+ 1) otherwise. Describe in terms of a single well-known arithmetic operation what f(n, 0) is computing.