* Ch. 4 of Discrete and Combinatorial Mathematics * * Exercise 4.1, problem 5a * 5. Consider the following program segment (written in pseudocode): for i := 1 to 123 do for j := 1 to i do print i * j
a) How many times is the print statement of the third line * executed? (n)(n+1)/2 * n = 123. The answer should be 7626 * * Exercise 4.2, problem 18a
Consider the permutations of 1, 2, 3, 4. The permutation 1432, for instance, is said to have one ascent—namely, 14 (since 1 < 4). This same permutation also has two descents— namely, 43 (since 4 > 3) and 32 (since 3 > 2). The permutation 1423, on the other hand, has two ascents, at 14 and 23—and the one descent 42. a) How many permutations of 1, 2, 3 have k ascents, for k _ 0, 1, 2?
Premutations of (1,2,3) have 1 zero ascent, 4 ascents of 1 and 1 ascent of 2 * * Ch. 4 of Discrete and Combinatorial Mathematics * * Exercise 4.3, problem 22a
In each of the following problems, we are using four-bit patterns for the two’s complement representations of the integers from −8 to 7. Solve each problem (if possible), and then convert the results to base 10 to check your answers. Watch for any overflow errors. 0101 * + 0001 * * * Exercise 4.4, problem 1a *
For each of the following pairs a, b ∈ Z+, determine gcd(a, b) and express it as a linear combination of a, b. a) 231, 1820 1820 = 7 (231) + 203 231 = 1 (203) + 28 203 = 7 (28) + 7 28 = 4 (7) gcd(1820, 231) = 7 7 = 203 – 7 (28) = 203 – 7 (231 – 203) = 8 (203) – 7 (231) = 8 (1820 – 7 (231)) – 7(231) * = 8 (1820) – 63 (231 * * Ch. 5 of Discrete and Combinatorial Mathematics * * Exercise 5.1, problem 4 * For which sets A, B is it true that AxB= BxA * * Exercise 5.2, problem 4 *
If there are 2187 functions f : A→B and |B| _ 3, whatis |A|?
* Exercise 5.3, problem 1a *
Give an example of finite sets A and B with |A|, |B| ≥ 4 and a function f : A→B such that (a) f is neither one-to-one nor onto
Consider A = {1,2,3,4,5} B = {a,b,c,d}
a) f is neither one-to-one nor onto f : {(1,a), (2, a), (5, c)}
