Discrete Mathematics Answers

Define a function A: N x N -> N as follows: A(m, n) ={2n, if m= 0; 0, if m≥1 and n= 0; 2, if m≥1 and n= 1; A(m-1, A(m, n-1)), if m≥1 and n≥2

Show that A(1, n) = 2^n whenever n≥1.
Hint: Induct on n.

Define a function A: N x N -> N as follows: A(m, n) ={2n, if m= 0; 0, if m≥1 and n= 0; 2, if m≥1 and n= 1; A(m-1, A(m, n-1)), if m≥1 and n≥2

Show that A(m, 2) = 4 whenever m≥1.
Hint: Induct on m.

Define a function A: N x N -> N as follows: A(m, n) ={2n, if m= 0; 0, if m≥1 and n= 0; 2, if m≥1 and n= 1; A(m-1, A(m, n-1)), if m≥1 and n≥2
(a) Calculate the following:
(i)A(1,0)
(ii)A(0,1)
(iii)A(1,1)
(iv)A(2,2).

Let S be a finite non-empty set. How many relations on S are simultaneously an equivalence relation and a partial order? Justify your answer.

Let S be a finite set, with |S|=n. If the bit matrix MR representing R contains exactly r entries that are 0, how many entries of MRbar are 0?

Note: "MRbar" is supposed to be just like MR, which you should know has R as a subscript, but with a bar over R. Just in case that got confusing.

(a) If A={1,2,3,4}, calculate the number of reflexive relations on A.
(b) If B={1,2,3,4,5}, calculate the number of symmetric relations on B.

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?