Week 2 Mth 221

* 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...