Week 3 Homework Essay examples

944 Words Jan 25th, 2014 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 ). o------o------o------o------o------o--- ...
…show more content…
=12! /9! (12-9)! = 220 220 entries = Troy has 220 ways to select nine marbles from a bag of twelve.
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 other numbers, is

Related Documents