Let S = R and let r be a binary relation on S defined by xry 4 x y is an integer. a

For each of the following binary relations r on N, decide which of the given ordered pairs belong to r. a. xry 4 x + y < 7; (1, 3), (2, 5), (3, 3), (4, 4) b. xry 4 x = y + 2; (0, 2), (4, 2), (6, 3), (5, 3) c. xry 4 2x + 3y = 10; (5, 0), (2, 2), (3, 1), (1, 3) d. xry 4 y is a perfect square; (1, 1), (4, 2), (3, 9), (25, 5)

For each of the following binary relations r on Z, decide which of the given ordered pairs belong to r. a. xry 4 x 0 y; (2, 6), (3, 5), (8, 4), (4, 8) b. xry 4 x and y are are relatively prime; (5, 8), (9, 16), (6, 8), (8, 21) c. xry 4 gcd(x, y) = 7; (28, 14), (7, 7), (10, 5), (21, 14) d. xry 4 x2 + y2 = z 2 for some integer z; (1, 0), (3, 9), (2, 2), (3, 4) e. xry 4 x is a number from the Fibonacci sequence; (4, 3), (7, 6), (7, 12), (20, 20

Decide which of the given items satisfy the relation. a. r a binary relation on Z, xry 4 x = y; (1, 1), (2, 2), (3, 3), (4, 4) b. r a binary relation on N, xry 4 x is prime; (19, 7), (21, 4), (33, 13), (41, 16) c. r a binary relation on Q, xry 4 x 1y; (1, 2), (3, 5), (4, 12), (12, 13) d. r a binary relation on N N, (x, y) r (u, v) 4 x + u = y + v; ((1, 2), (3, 2)), ((4, 5), (0, 1))

Decide which of the given items satisfy the relation. a. \(\rho\) a binary relation on \(S \times C\) where S = {states in the United States}, C = {cities in the United States}, \(x \rho y \leftrightarrow y\) is the capital of x; (Indiana, Indianapolis), (Illinois, Chicago), (Kansas, Kansas City), (Kentucky, Louisville), (North Dakota, Bismarck) b. \(\rho\) a binary relation on \(A \times P\) where A = {artists}, P = {paintings}, \(x \rho y \leftrightarrow y\) composed y; (DaVinci, Mona Lisa), (Grant Wood, American Gothic), (Remington, Ridden Down), (Picasso, Blue Dancers), (van Gogh, Starry Night) c. \(\rho\) a binary relation on \(C \times M\) where C = {composers}, M = {music}, \(x \rho y \leftrightarrow y\) composed y; (Bernstein, West Side Story), (Presley, Blue Suede Shoes), (Gershwin, Rhapsody in Blue), (Beethoven, Moonlight Sonata), (Rogers and Hammerstein, Phantom of the Opera) d. \(\rho\) a binary relation on \(A \times B\), where A = {authors}, B = {books}, \(x \rho y \leftrightarrow y\) wrote y; (Hemingway, The Old Man and the Sea), (Sawyer, Huckleberry Finn) (Poe, Moby Dick), (Orwell, 1984), (Tolstoy, Crime and Punishment)

For each of the following binary relations on R, draw a figure to show the region of the plane it describes. a. xry 4 y 2 b. xry 4 x = y 1 c. xry 4 x2 + y2 25 d. xry 4 x y

For each of the accompanying figures, give the binary relation on R that describes the shaded area

Identify each relation on N as one-to-one, one-to-many, many-to-one, or many-to-many. a. r = 5(1, 2), (1, 4), (1, 6), (2, 3), (4, 3)6 b. r = 5(9, 7), (6, 5), (3, 6), (8, 5)6 c. r = 5(12, 5), (8, 4), (6, 3), (7, 12)6 d. r = 5(2, 7), (8, 4), (2, 5), (7, 6), (10, 1)6

Identify each of the following relations on S as one-to-one, one-to-many, many-to-one, or many-to-many. a. S = N xry 4 x = y + 1 b. S = set of all women inVicksburg xry 4 x is the daughter of y c. S = `(51, 2, 36) ArB 4 0A0 = 0B0 d. S = R xry 4 x = 5

Let r and s be binary relations on N defined by xry 4 x divides y, xsy 4 5x y. Decide which of the given ordered pairs satisfy the following relations. a. r c s; (2, 6), (3, 17), (2, 1), (0, 0) b. r d s; (3, 6), (1, 2), (2, 12) c. r; (1, 5), (2, 8), (3, 15) d. s; (1, 1), (2, 10), (4, 8

Both r and s are binary relations from P to C where P = 5people in theUnited States6, C = 5cities in the United States6, xry 4 x lives in y, and xsy 4 x works in y. Describe each of the following relations. a. r d s c. r d s b. r c s d. r d s

Let S = 51, 2, 36. Test the following binary relations on S for reflexivity, symmetry, antisymmetry, and transitivity. a. r = 5(1, 3), (3, 3), (3, 1), (2, 2), (2, 3), (1, 1), (1, 2)6 b. r = 5(1, 1), (3, 3), (2, 2)6 c. r = 5(1, 1), (1, 2), (2, 3), (3, 1), (1, 3)6 d. r = 5(1, 1), (1, 2), (2, 3), (1, 3)6

Let S = 50, 1, 2, 4, 66. Test the following binary relations on S for reflexivity, symmetry, antisymmetry, and transitivity. a. r = 5(0, 0), (1, 1), (2, 2), (4, 4), (6, 6), (0, 1), (1, 2), (2, 4), (4, 6)6 b. r = 5(0, 1), (1, 0), (2, 4), (4, 2), (4, 6), (6, 4)6 c. r = 5(0, 1), (1, 2), (0, 2), (2, 0), (2, 1), (1, 0), (0, 0), (1, 1), (2, 2)6 d. r = 5(0, 0), (1, 1), (2, 2), (4, 4), (6, 6), (4, 6), (6, 4)6 e. r = [

Test the following binary relations on the given sets S for reflexivity, symmetry, antisymmetry, and transitivity. a. S = Q xry 4 0x0 0y0 b. S = Z xry 4 x y is an integral multiple of 3 c. S = N xry 4 x # y is even d. S = N xry 4 x is odd e. S = set of all squares in the plane S1r S2 4 length of side of S1 = length of side of S2

Test the following binary relations on the given sets S for reflexivity, symmetry, antisymmetry, and transitivity. a. S = set of all finite-length strings of characters xry 4 number of characters in x = number of characters in y b. S = 50, 1, 2, 3, 4, 56 xry 4 x + y = 5 c. S = `(51, 2, 3, 4, 5, 6, 7, 8, 96) A rB 4 0A0 = 0B0 d. S = `(51, 2, 3, 4, 5, 6, 7, 8, 96) ArB 4 0A0 0B0 e. S = N N (x1, y1)r(x2, y2) 4 x1 x2 and y1 y2

Which of the binary relations of Exercise 13 are equivalence relations? For each equivalence relation, describe the associated equivalence classes

Which of the binary relations of Exercise 14 are equivalence relations? For each equivalence relation, describe the associated equivalence classes.

Test the following binary relations on the given sets S for reflexivity, symmetry, antisymmetry, and transitivity. a. S = Z xry 4 x + y is a multiple of 5 b. S = Z xry 4 x < y c. S = set of all finite-length binary strings xry 4 x is a prefix of y d. S = set of all finite-length binary strings xry 4 x has the same number of 1s as y

Test the following binary relations on the given sets S for reflexivity, symmetry, antisymmetry, and transitivity. a. S = Z xry 4 x = ky for some integer k b. S = Z xry 4 there is a prime number p such that p 0 x and p 0 y c. S = `(51, 2, 3, 4, 5, 6, 7, 8, 96) ArB 4 A d B = [ d. S = `(51, 2, 3, 4, 5, 6, 7, 8, 96) ArB 4 A = B

Let S be the set of people in the United States. Test the following binary relations on S for reflexivity, symmetry, antisymmetry, and transitivity. a. \(x \rho \ y \leftrightarrow x\) is at least as tall as y. b. \(x \rho \ y \leftrightarrow x\) is taller than y. c.\(x \rho \ y \leftrightarrow x\) is the same height

Let S be the set of people in the United States. Test the following binary relations on S for reflexivity, symmetry, antisymmetry, and transitivity. a. \(x \rho y \leftrightarrow x\) is the husband of y. b. \(x \rho y \leftrightarrow x\) is the spouse of y. c. \(x \rho y \leftrightarrow x\) has the same parents as y. d. \(x \rho y \leftrightarrow x\) is the brother of y.

For each case, think of a set S and a binary relation r on S (different from any in the examples or problems) satisfying the given conditions. a. r is reflexive and symmetric but not transitive. b. r is reflexive and transitive but not symmetric. c. r is not reflexive or symmetric but is transitive. d r is reflexive but neither symmetric nor transitive.

Let \(\rho\) and \(\sigma\) be binary relations on a set S. a. If \(\rho\) and \(\sigma\) are reflexive, is \(\rho \cup \sigma\) reflexive? Is \(\rho \cap \sigma\) reflexive? b. If \(\rho\) and \(\sigma\) are symmetric, is \(\rho \cup \sigma\) symmetric? Is \(\rho \cap \sigma\) symmetric? c. If \(\rho\) and \(\sigma\) are antisymmetric, is \(\rho \cup \sigma\) antisymmetric? Is \(\rho \cap \sigma\) antisymmetric? d. If \(\rho\) and \(\sigma\) are transitive, is \(\rho \cup \sigma\) transitive? Is \(\rho \cap \sigma\) transitive?

Find the reflexive, symmetric, and transitive closure of each of the relations in Exercise 11.

Find the reflexive, symmetric, and transitive closure of each of the relations in Exercise 12

Given the following binary relation S = set of all cities in the country \(x \rho y \leftrightarrow\) Take-Your-Chance Airlines flies directly from x to y describe in words what the transitive closure relation would be.

Two additional properties of a binary relation r are defined as follows: r is irreflexive means: (4x)(x [ S S (x, x) o r) r is asymmetric means: (4x)(4y)(x [ S ` y [ S ` (x, y) [ r S (y, x) o r) a. Give an example of a binary relation r on set S = 51, 2, 36 that is neither reflexive nor irreflexive. b. Give an example of a binary relation r on set S = 51, 2, 36 that is neither symmetric nor asymmetric. c. Prove that if r is an asymmetric relation on a set S, then r is irreflexive. d. Prove that if r is an irreflexive and transitive relation on a set S, then r is asymmetric. e. Prove that if r is a nonempty, symmetric, and transitive relation on a set S, then r is not irreflexive

Does it make sense to look for the irreflexive closure of a relation? (See Exercise 26.) Why or why not?

Does it make sense to look for the asymmetric closure of a relation? (See Exercise 26.) Why or why not?

Let S be an n-element set. How many different binary relations can be defined on S? (Hint: Recall the formal definition of a binary relation.)

Let r be a binary relation on a set S. For A # S, define [A = 5x 0 x [ S ` (4y)(y [ A S xry)6 A[ = 5x 0 x [ S ` (4y)(y [ A S yrx)6 a. Prove that if r is symmetric, then [A = A[. b. Prove that if A # B then [B # [A and B[ # A[. c. Prove that A # ([A)[. d. Prove that A # [(A[)

Draw the Hasse diagram for the following partial orderings. a. S = 5a, b, c6 r = 5(a, a), (b, b), (c, c), (a, b), (b, c), (a, c)6 b. S = 5a, b, c, d6 r = 5(a, a), (b, b), (c, c), (d, d), (a, b), (a, c)6 c. S = 5[, 5a6, 5a, b6, 5c6, 5a, c6, 5b66 ArB 4 A # B

For Exercise 31, name any least elements, minimal elements, greatest elements, and maximal elements.

Let (S, d) be a partially ordered set, and let A # S. Prove that the restriction of d to A is a partial ordering on A.

a. Draw the Hasse diagram for the partial ordering “x divides y” on the set {2, 3, 5, 7, 21, 42, 105, 210}. Name any least elements, minimal elements, greatest elements, and maximal elements. Name a totally ordered subset with four elements. b. Draw the Hasse diagram for the partial ordering “x divides y” on the set {3, 6, 9, 18, 54, 72, 108, 162}. Name any least elements, minimal elements, greatest elements, and maximal elements. Name any unrelated elements.

Draw the Hasse diagram for each of the two partially ordered sets. a. S = 51, 2, 3, 5, 6, 10, 15, 306 b. S = `(51, 2, 36) xry 4 x divides y ArB 4 A # B What do you notice about the structure of these two diagrams?

For each Hasse diagram of a partial ordering in the accompanying figure, list the ordered pairs that belong to the relation.

Let (S, r) and (T, s) be two partially ordered sets. A relation m on S T is defined by (s1, t1) m(s2, t2) 4 s1rs2 and t1st2. Show that m is a partial ordering on S T.

Let \(\rho\) be a binary relation on a set S. Then a binary relation called the inverse of \(\rho\), denoted by \(\rho^{-1}\), is defined by \(x \rho^{-1} y \leftrightarrow y \rho x\) a. For \(\rho=\{(1,2),(2,3),(5,3),(4,5)\}\) on the set \(\mathbb{N}\), what is \(\rho^{-1}\) ? b. Prove that if \(\rho\) is a reflexive relation on a set S, then \(\rho^{-1}\) is reflexive. c. Prove that if \(\rho\) is a symmetric relation on a set S, then \(\rho^{-1}\) is symmetric. d. Prove that if \(\rho\) is an antisymmetric relation on a set S, then \(\rho^{-1}\) is antisymmetric. e. Prove that if \(\rho\) is a transitive relation on a set S, then \(\rho^{-1}\) is transitive. f. Prove that if \(\rho\) is an irreflexive relation on a set S (see Exercise 26), then \(\rho^{-1}\) is irreflexive. g. Prove that if \(\rho\) is an asymmetric relation on a set S (see Exercise 26), then \(\rho^{-1}\) is asymmetric.

Prove that if a binary relation r on a set S is reflexive and transitive, then the relation r d r1 is an equivalence relation (see Exercise 38 for the definition of r1 ).

a. Let (S, r) be a partially ordered set. Then r1 can be defined as in Exercise 38. Show that (S, r1 ) is a partially ordered set, called the dual of (S, r). a. b. c. Section 5.1 Relations 351 b. If (S, r) is a finite, partially ordered set with the Hasse diagram shown, draw the diagram of the dual of (S, r). c. Let (S, r) be a totally ordered set and let X = 5(x, x) 0 x [ S6. Show that the setdifference r1 X equals the set r.

A computer program is to be written that will generate a dictionary or the index for a book. We will assume a maximum length of n characters per word. Thus, we are given a set S of words of length at most n, and we want to produce a linear list of these words arranged in alphabetical order. There is a natural total ordering \(\preceq\) on alphabetic characters \((a \prec \ b, b \prec \ c\), etc.\()\), and we will assume our words contain only alphabetic characters. We want to define a total ordering \(\preceq\) on S called a lexicographical ordering that will arrange the members of S alphabetically. The idea is to compare two words X and Y character by character, passing over equal characters. If at any point the X character alphabetically precedes the corresponding Y character, then X precedes Y; if all characters in X are equal to the corresponding Y characters but we run out of characters in X before characters in Y, then X precedes Y. Otherwise, Y precedes X. Formally, let \(X=\left(x_1, x_2, \ldots, x_j\right)\) and \(Y=\left(y_1, y_2, \ldots, y_k\right)\) be members of S with \(j \leq k\). Let \(\beta\) (for blank) be a new symbol, and fill out X with k - j blanks on the right. X can now be written \(\left(x_1, x_2, \ldots, x_k\right)\). Let \(\beta\) precede any alphabetical character. Then \(X \preceq Y\) if \(x_1 \neq y_1 \text { and } x_1 \preceq y_1\) or \(\begin{aligned}& x_1=y_1, x_2=y_2, \ldots, x_m=y_m(m \leq k) \\& x_{m+1} \neq y_{m+1} \text { and } x_{m+1} \preceq y_{m+1}\end{aligned}\) Otherwise, \(Y \preceq X\). Note that because the ordering \(\preceq\) on alphabetical characters is a total ordering, if \(Y \preceq X\) by "otherwise," then there exists \(m \leq k\) such that \(x_1=y_1, x_2=y_2, \ldots, x_m=y_m, x_{m+1} \neq y_{m+1}\) and \(y_{m+1} \leqslant x_{m+1}\). Show that \(\preceq\) on S as defined above is a total ordering.

Apply the total ordering described in Exercise 41 to the words boo, bug, be, bah, and bugg. Note why each word precedes the next.

Exercise 41 discusses a total ordering on a set of words of length at most n that will produce a linear list in alphabetical order. Suppose we want to generate a list of all the distinct words in a text (for example, a compiler must create a symbol table of variable names). As in Exercise 41, we assume that the words contain only alphabetical characters because there is a natural precedence relation already existing (a a b, b a c, and so on). If numeric or special characters are involved, they must be assigned a 352 Relations, Functions, and Matrices precedence relation with alphabetical characters (the collating sequence must be determined). If we list words alphabetically, it is a fairly quick procedure to decide whether a word currently being processed is new, but to fit the new word into place, all successive words must be moved one unit down the line. If the words are listed in the order in which they are processed, new words are simply tacked onto the end and no rearranging is necessary, but each word being processed has to be compared with each member of the list to determine if it is new. Thus, both logical linear lists have disadvantages. We describe a structure called a binary search tree; using this structure, a search process called a binary tree search can usually determine quickly whether a word is new and, if it is, no juggling is required to fit it into place, thus eliminating the disadvantages of both linear list structures described earlier. Suppose we want to process the phrase when in the course of human events. The first word in the text is used to label the first node of a graph. Once a node is labeled, it drops down a left and right arc, putting two unlabeled nodes below the one just labeled. when when When the next word in the text is processed, it is compared with the first node. When the word being processed alphabetically precedes the label of a node, the left arc is taken; when the word follows the label alphabetically, the right arc is taken. The word becomes the label of the first unlabeled node it reaches. (If the word equals a node label, it is a duplicate, so the next word in the text is processed.) This procedure continues for the entire text. Thus, when in then when in the then when in course the Section 5.1 Relations 353 until finally when in course human events of the By traversing the nodes of this graph in the proper order (described by always processing the left nodes below a node first, then the node, then the right nodes below it), an alphabetical listing course, events, human, in, of, the, when is produced. a. This type of graph is called a tree. (Unlabeled nodes and arcs to unlabeled nodes usually are not shown.) Turned upside down, the graph can be viewed as the Hasse diagram of a partial ordering d. What would be the least element? Would there be a greatest element? Which of the following ordered pairs would belong to d: (in, of), (the, of), (in, events), (course, of)? Here the tree structure contains more information than the partial ordering, because we are interested in not only whether a word w1 precedes a word w2 in the partial ordering sense but also whether w2 is to the left or right of w1. b. Build a binary search tree for the phrase Old King Cole was a merry old soul. Eliminate unlabeled nodes. Considering the upside-down graph as the Hasse diagram of a partial ordering, name the maximal elements.

The alphabetical ordering defined in Exercise 41 can be applied to words of any finite length. If we define A* to be the set of all finite-length “words” (strings of characters, not necessarily meaningful) from the English alphabet, then the alphabetical ordering on A* has all words composed only of the letter A preceding all other words. Thus, all the words in the infinite list a, aa, aaa, aaaa, ... precede words such as “b” or “aaaaaaab.” Therefore this list does not enumerate A*, because we can never count up to any words with any characters other than a. However, the set A* is denumerable. Write a partial enumeration of A* by ordering words by length (all words of length 1 precede all words of length 2, and so on) and then alphabetically ordering words of the same length.

a. For the equivalence relation r = 5(a, a), (b, b), (c, c), (a, c), (c, a)6, what is the set [a]? Does it have any other names? b. For the equivalence relation r = 5(1, 1), (2, 2), (1, 2), (2, 1), (1, 3), (3, 1), (3, 2), (2, 3), (3, 3), (4, 4), (5, 5), (4, 5), (5, 4)6 what is the set [3]? What is the set [4]?

Prove that for any positive integer n, congruence modulo n is an equivalence relation on the set Z

For the equivalence relation of congruence modulo 2 on the set Z, what is the set [1]?

For the equivalence relation of congruence modulo 5 on the set Z, what is the set [3]?

Assume that x y (mod n) and z w (mod n) for some positive integer n. Prove that a. x + z y + w (mod n) b. x z y w (mod n) c. x # z y # w (mod n) d. xs ys (mod n) for s 1, n 2

Let p be a prime number. Prove that x2 y2 (mod p) if and only if x y (mod p) or x y (mod p).

a. Given the partition 51, 26 and 53, 46 of the set S = 51, 2, 3, 46, list the ordered pairs in the corresponding equivalence relation. b. Given the partition 5a, b, c6 and 5d, e6 of the set S = 5a, b, c, d, e6, list the ordered pairs in the corresponding equivalence relation

Let S be the set of all books in the library. Let r be a binary relation on S defined by xry 4 the color of xs cover is the same as the color of ys cover. Show that r is an equivalence relation on S and describe the resulting equivalence classes.

Let S = N and let r be a binary relation on S defined by xry 4 x2 y2 is even. Show that r is an equivalence relation on S and describe the resulting equivalence classes.

Let S = R and let r be a binary relation on S defined by xry 4 x y is an integer. a. Show that r is an equivalence relation on S. b. List 5 values that belong to [1.5].

Let \(S =\mathbb {N} \times \mathbb {N}\) and let r be a binary relation on S defined by \((x, y)\rho(z, w) \leftrightarrow y = w\). Show that \(\rho\) is an equivalence relation on S and describe the resulting equivalence classes.

Let S = N N and let r be a binary relation on S defined by (x, y)r(z, w) 4 x + y = z + w. Show that r is an equivalence relation on S and describe the resulting equivalence classes

Let S be the set of all binary strings of length 8 and let r be a binary relation on S defined by xry 4 y starts with the same bit value (0 or 1) as x and y ends with the same bit value (0 or 1) as x. a. Show that r is an equivalence relation on S. b. How many strings are in the set S? c. Into how many equivalence classes does r partition S? Explain your answer. d. How many strings are in each equivalence class?

The documentation for the Java programming language recommends that when a boolean equals method is defined for an object, it should be an equivalence relation. That is, if r is defined by xry 4 x.equals(y) for all objects in the class, then r should be an equivalence relation. In a graphics application, a programmer creates an object called a point, consisting of two coordinates in the plane. The programmer defines an equals method as follows: If p and q are any two points in the plane, then p.equals(q) 4 the distance from p to q is c where c is a small positive number that depends on the resolution of the computer display. Is the programmers equals method an equivalence relation? Justify your answer.

Let S be the set of all propositional wffs with n statement letters. Let r be a binary relation on S defined by PrQ 4 P 4 Q is a tautology. Show that r is an equivalence relation on S and describe the resulting equivalence classes. (We have used the notation P 3 Q for PrQ.)

Given two partitions p1 and p2 of a set S, p1 is a refinement of p2 if each block of p1 is a subset of a block of p2. Show that refinement is a partial ordering on the set of all partitions of S.

Let Pn denote the total number of partitions of an n-element set, n 1. The numbers Pn are called Bell numbers. Compute the following Bell numbers. a. P1 b. P2 c. P3 d. P4

From Exercise 61, you might be looking for a closed-form formula giving the value of \(P_n\). Although Bell numbers have been extensively studied, no closed-form formula has been found. Bell numbers can be computed via a recurrence relation. Let \(P_0\) have the value 1 . Prove that for \(n \geq 1\), \(P_n=\sum_{k=0}^{n-1} C(n-1, k) P_k\) (Hint: Use a combinatorial proof instead of an inductive proof. Let x be a fixed but arbitrary member of a set with n elements. In each term of the sum, n - k represents the size of the partition block that contains x.)

. Use the formula of Exercise 62 to compute P1, P2, P3, and P4, and compare your answers to those in Exercise 61.

Use the formula of Exercise 62 to compute P5 and P

Let S(n, k) denote the number of ways to partition a set of n elements into k blocks. The numbers S(n, k) are called Stirling numbers. a. Find S(3, 2). b. Find S(4, 2).

Prove that for all n 1, S(n, k) satisfies the recurrence relation S(n, 1) = 1 S(n, n) = 1 S(n + 1, k + 1) = S(n, k) + (k + 1)S(n, k + 1) for 1 k n (Hint: Use a combinatorial proof instead of an inductive proof. Let x be a fixed but arbitrary member of a set with n + 1 elements, and put x aside. Partition the remaining set of n elements. A partition of the original set could be obtained either by adding 5x6 as a separate block or by putting x in one of the existing blocks.)

Prove that for all n 1, S(n, k) satisfies the recurrence relation S(n, 1) = 1 S(n, n) = 1 S(n + 1, k + 1) = S(n, k) + (k + 1)S(n, k + 1) for 1 k n (Hint: Use a combinatorial proof instead of an inductive proof. Let x be a fixed but arbitrary member of a set with n + 1 elements, and put x aside. Partition the remaining set of n elements. A partition of the original set could be obtained either by adding 5x6 as a separate block or by putting x in one of the existing blocks.)

Prove that for all n 1, S(n, k) satisfies the recurrence relation S(n, 1) = 1 S(n, n) = 1 S(n + 1, k + 1) = S(n, k) + (k + 1)S(n, k + 1) for 1 k n (Hint: Use a combinatorial proof instead of an inductive proof. Let x be a fixed but arbitrary member of a set with n + 1 elements, and put x aside. Partition the remaining set of n elements. A partition of the original set could be obtained either by adding 5x6 as a separate block or by putting x in one of the existing blocks.)

Use the formula of Exercise 69 and Stirlings triangle (Exercise 68) to compute P1, P2, P3, and P4.

Find the number of ways to distribute 4 different-colored marbles among 3 identical containers so that no container is empty

Find the number of ways to distribute 4 different-colored marbles among 3 identical containers so that no container is empty.

Binary relations on a set S are ordered pairs of elements of S. More generally, an n-ary relation on a set S is a set of ordered n-tuples of elements of S. Decide which of the given items satisfy the relation. a. r a unary relation on Z, x [ r 4 x is a perfect square 25, 39, 49, 62 b. r a ternary relation on N, (x, y, z) [ r 4 x2 + y2 = z 2 (1, 1, 2), (3, 4, 5), (0, 5, 5), (8, 6, 10) c. r a 4-ary relation on Z, (x, y, z, w) [ r 4 y = 0x0 and w x + z 2 (4, 4, 2, 0), (5, 5, 1, 5), (6, 6, 6, 45), (6, 6, 0, 2)

Binary relations on a set S are ordered pairs of elements of S. More generally, an n-ary relation on a set S is a set of ordered n-tuples of elements of S. Decide which of the given items satisfy the relation. a. r a unary relation on Z, x [ r 4 x is a perfect square 25, 39, 49, 62 b. r a ternary relation on N, (x, y, z) [ r 4 x2 + y2 = z 2 (1, 1, 2), (3, 4, 5), (0, 5, 5), (8, 6, 10) c. r a 4-ary relation on Z, (x, y, z, w) [ r 4 y = 0x0 and w x + z 2 (4, 4, 2, 0), (5, 5, 1, 5), (6, 6, 6, 45), (6, 6, 0, 2)

A ternary relation r is defined on the set S = (2, 4, 6, 8) by (x, y, z) [ r 4 x + y = z. List the 3-tuples that belong to r.

If x is a real number, \(x \neq 0\), then a number y such that \(x \cdot y=1\) is called the multiplicative inverse of x. Given positive integers x and n, a positive integer y such that \(x \cdot y \equiv 1(\bmod n)\) is called the modular multiplicative inverse of x modulo n. But \(\begin{aligned} & x \cdot y \equiv 1(\bmod n) \\ \leftrightarrow & x \cdot y-1=k n \text { where } k \text { is an integer } \\ \leftrightarrow & x y-k n=1 \\ \leftrightarrow & 1 \text { is a linear combination of } x \text { and } n \\ \leftrightarrow & \operatorname{gcd}(x, n)=1 \\ \leftrightarrow & x \text { and } n \text { are relatively prime }\end{aligned}\) Thus, if x and n are not relatively prime, the modular inverse of x does not exist. If they are relatively prime, the modular inverse of x is the positive coefficient of x in the linear combination of x and n that equals 1 . Use the Euclidean algorithm to find the modular multiplicative inverse of 21 modulo 25 (note that 21 and 25 are relatively prime).

Use the Euclidean algorithm to find the modular multiplicative inverse of 68 modulo 15 (see Exercise 75).