947 words - 4 pages

Week 3 homework

Exercise 7.1, problem 10a

The total number of pairs we can either include or not is 4^2-4=16. Any reflexive relation is a subset of this set of 12 elements; we know there are 2^12 such subsets.

Problem 10b

The number of decisions we can make for any symmetric relation is 4+ (16-4)/2=4+6=10.

The number of possible symmetric relations is 210.

Exercise 7.2, Problem 15a

a) Draw the digraph G1 (V1, E1) where V1 {a, b, c,

d, e, f } and E1 {(a, b), (a, d), (b, c), (b, e), (d, b),

(d, e), (e, c), (e, f), (f, d)}.

Exercise 7.3, Problem 1

Draw the Hasse diagram for the poset ⊆, where{1, 2, 3, 4}.

(1,1)<(1,2)<(1,3)<(1,4)<(2,1)<(2,2)<...<(4,3)<(4,4 ...view middle of the document...

Exercise 8.2, Problem 4

a) We need to find the number of sequences with exactly 4 distinct numbers.

There are (7 choose 4) ways of choosing four numbers, say a_1, a_2, a_3, a_4 from the numbers 1 through 7.

Now we need to find the number of sequences that contain the selected numbers a_1, a_2, a_3, a_4 each at least once, but contain no other numbers.

There are 4^10 sequences that contain no other numbers besides a_1, a_2, a_3, a_4. Now we restrict our attention to these 4^10 sequences only.

Out of these 4^10 sequences, the number of sequences that are *missing* at least one of a_1, a_2, a_3, a_4, by the inclusion-exclusion principle, is

sum of numbers of sequences missing a_i's taken one at a time - sum of numbers of sequences missing a_i's taken two at a time + sum of numbers of sequences missing a_i's taken three at a time - sum of numbers of sequences missing a_i's taken four at a time

= (4 choose 1)*3^10 - (4 choose 2)*2^10 + (4 choose 3)*1^10

- (4 choose 4)*0^10. So the number of sequences that contain the selected numbers a_1, a_2, a_3, a_4 each at least once, but contain no...

Find the perfect research document on any subject