Classification of Combinatorial problems i Order matters does not matter Choose a committee of 3 out of 10 members members are distinguishable the order of the members in committee does not matter 10 10 9 8 C 10 3 3 7 3 Choose president vice president and secretary out of 10 members three different assignments mean the order is important 10 9 8 1 ii identical objects Count different arrangements of 4 objects AABC Modify the problem AaBC Then we have 4 24 distinguishable arrangements For any positions of B and C we have 2 choices that should not be distinguished So only 24 2 12 arrangements are distinct Count arrangements of AABB 12 2 6 2 iii with without repetitions How many distinct 3 letter passwords exist order is important abc bac Any letter can be used only once without repetition 26 25 24 many times with repetition 263 You draw 3 balls from a box with 10 red 10 blue and 10green order is not important rbg brg gbr 3 A committee of 3 is to be chosen from 5 Democrats 3 Republicans and 4 Independents a In how many ways it can be done all representatives are not distinguished all members of a committee are equivalent selections with repetition the same problem 5 red 3 blue and 4 green balls are picked at random How many different outcomes are possible 5 10 3 2 DDD DDR DRR RRR III IDD IDR IRR IIR IID 4 Consider the situation when all representatives are distinguished What will be the number of possible committees C 12 3 b In how many ways it can be done if the committee must contain at least one independent We must put one star in the independent box and count different ways to distribute two remaining stars in three boxes DDI DRI DII RRI D R I RII 2 2 III 6 5 2 2 For what situations the following answers apply 12 11 10 12 5 4 3 3 distinguished positions in the committee and all representatives are distinguished 12 distinguished positions in the committee representatives of a party are not distinguished 6 In how many ways can we select three books each from different subject from a set of 6 distinct history books 9 distinct classic books 7 distinct law books and 4 distinct education books C 6 3 C 9 3 C 7 3 C 4 3 An exam has 12 problems How many ways can integer points be assigned to the problems if the total of the points is 100 and each problem is worth at least five points x1 x2 x12 100 40 11 40 11 xi 5 7 Find the formula involving the connectives and that has the following truth table q r 1 1 0 0 1 0 1 0 q r 1 1 0 1 You can observe that q r r q r q 8 Let be an unknown boolean logical operator The logical statement p q r q r is equivalent to p q r Given this information there are 2 possible truth tables for the boolean logical operator List both of these truth tables p q r 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 p q 1 1 0 0 0 0 0 0 p q r 1 1 1 0 1 0 1 0 p q r p q r q r 1 0 1 1 1 1 1 1 q r 1 0 1 1 0 1 1 0 1 1 0 9 Answer q r q r 1 1 0 0 1 0 1 0 1 1 0 1 0 10 Use laws of logic to show that the following expression is a tautology p p q q r q r p q q r q p q r q p r p q q r q r q p r q r q q p r r T p r r T p T T 11 In each case determine whether or not two propositions are logically equivalent x p x q x x p x x q x x p x q x x p x x q x x p x q x x p x x q x x p x q x x p x x q x 12 Suppose A B and C is any set Prove or disprove that C B C A C C B A Proof Given A B A B C A Goal C B C A 13 Given A B Goal C B C A x C B x C A Contrapositive x C A x C B A B x C A x C B x C x A x C x A x C x B x C x B x C B 14
View Full Document
Unlocking...