Some Simple Counting Rules - Hamilton Institute

1 some Simple Counting RulesEE304 - Probability and StatisticsSemester 1 some Simple Counting RulesCountingIf all outcomes are equally likely, the probability of an eventEisgiven by|E||S|where|E|(|S|) denotes the number of elements inE(S).To apply this rule, we need to be able to count the number ofelements in events. We shall look at:Multiplication Rules ;Permutations of distinct objects;Permutations where some objects are identical;Combinations . some Simple Counting RulesSome Simple Counting RulesMultiplication Rule Basic ideaIf one operation can be done inn1ways and a second operationcan be done inn2ways then the number of different ways of doingboth we roll a fair die and toss a coin, the total number ofpossible outcomes is 6 2 = we roll a fair 4-sided die 3 times.

2 The total number ofpossible outcomes is 4 4 4 = Simple Counting RulesSome Simple Counting RulesMultiplication Rule Basic ideaIf one operation can be done inn1ways and a second operationcan be done inn2ways then the number of different ways of doingboth we roll a fair die and toss a coin, the total number ofpossible outcomes is 6 2 = we roll a fair 4-sided die 3 times, the total number ofpossible outcomes is 4 4 4 = Simple Counting RulesSome Simple Counting RulesExampleA Simple survey consists of three multiple choice questions. Thefirst question has 3 possible answers, the second has 4 possibleanswers and the third has 3 possible answers.

3 What is the totalnumber of different ways in which this survey could be completed?3 4 3 = circuit board contains 4 relays each of which can be set to anyof three positions. What is the total number of distinctconfigurations for the 4 relays?Each relay can be set in 3 ways and we have 4 the total number of configurations is (3)(3)(3)(3) = Simple Counting RulesSome Simple Counting RulesExampleA Simple survey consists of three multiple choice questions. Thefirst question has 3 possible answers, the second has 4 possibleanswers and the third has 3 possible answers. What is the totalnumber of different ways in which this survey could be completed?

4 3 4 3 = circuit board contains 4 relays each of which can be set to anyof three positions. What is the total number of distinctconfigurations for the 4 relays?Each relay can be set in 3 ways and we have 4 the total number of configurations is (3)(3)(3)(3) = Simple Counting RulesPermutationsHow many different arrangements/permutations ofndistinctobjects are possible?The first object can be chosen innways;The second object can then be chosen inn 1 ways and soon;The number of ways of permuting (arranging in order)ndistinguishable objects isn (n 1) (n 2) 3 2 1Or compactly,n! (nfactorial). some Simple Counting RulesPermutationsThe total number of different ways in which the letters of theword count can be arranged is 5!

5 = (5)(4)(3)(2)(1) = is important here that the letters are all horses run a race. The total number of possible results ofthis race (assuming no ties) is 6! = (6)(5)(4)(3)(2)(1) = search engine ranks 11 websites related to a particular queryin order of relevance. How many different rankings arepossible? Answer 11!. some Simple Counting RulesPermutationsWhat if not all the objects are distinct?What is the total number of different arrangements of theletters in the word stat ?Suppose the two t s can be we would have 4! arrangement of the original word stat would generate2! arrangements the number of arrangements of the word stat is4!

6 2!= Simple Counting RulesPermutations with some Objects IdenticalIn general if we havenitemskof which are identical, the totalnumber of distinct permutations isn!k!.ExampleHow many different ways can we arrange the letters BBBACDE?Answer7!3!= (7)(6)(5)(4) = many different numbers can be formed by rearranging2212562?Answer7!4!= Simple Counting RulesPermutations with some Objects IdenticalExampleHow many different ways can we rearrange the letters ofMISSISSIPPI?MISPISPISISWe have 11 letters in total, of which 4 are I , 4 are S and 2 are P . In this situation, the total number of different rearrangementsis11!

7 4!4!2!. some Simple Counting RulesSome Simple Counting Rulesr-PermutationsHow many permutations ofndistinct objects, takenrat a timeare possible?Again, we havenways of choosing the first then haven 1 ways of choosing the second object andso choosing therthobject, we have already chosenr 1objects, so there are stilln (r 1) =n r+ 1 Simple Counting RulesPermutationsThe total number ofrpermutations of a set ofndistinguishable objects isn (n 1) (n r+ 1).There arerterms in the number ofr-permutations of a set ofndistinguishable objectsis !(n r)!. some Simple Counting RulesExamplesExampleIn a race with eight competitors, how many differentpossibilities are there for who finishes finish first, second andthird?

8 Three major new roads are to be constructed and eightcompanies have tendered for the three projects. If at most oneconstruction project is to be given to any one company, whatis the total number of ways in which the three contracts canbe awarded?Both of these have the same answer Simple Counting RulesExamplesExampleIn a race with eight competitors, how many differentpossibilities are there for who finishes finish first, second andthird?Three major new roads are to be constructed and eightcompanies have tendered for the three projects. If at most oneconstruction project is to be given to any one company, whatis the total number of ways in which the three contracts canbe awarded?

9 Both of these have the same answer Simple Counting RulesSome Simple Counting RulesCombinationsHow many different ways can we select a set of sizerfrom a largerset ofndistinguishable objects? The order of selection does are asking for the number of combinations ofnobjects takenrat a time. This number is written as(nr).Each combination/set ofr-objects can be permuted in exactlyr! distinct ways;This means that(nr)=nPrr!=n!r!(n r)!.Note that(nr)=(nn r). some Simple Counting RulesCounting - ExamplesExampleHow many ways can a company select 3 candidates tointerview from a short list of 15?Answer(153)=(15)(14)(13)(3)(2)(1)= 455In how many ways can a subcommittee of 5 be chosen from apanel of 20?

10 Answer(205)=(20)(19)(18)(17)(16)(5)(4)(3 )(2)(1)= Simple Counting RulesCombinations - ExamplesExampleA drum contains 3 black balls, 5 red balls and 6 green balls. If 4balls are selected at random what is the probability that the 4selected contain(i) No red ball?(ii) Exactly 1 black ball?(iii) Exactly 1 red ball and exactly 2 green balls? some Simple Counting RulesExamplesExample(i) Total number of ways of choosing 4 balls from 14 is(144).Total number of ways of choosing 4 balls, none of which is red is(94).So the probability that the 4 balls contain no red ball is(94)(144).(ii) 1 black ball can be chosen in(31)ways, while the other threeballs can be chosen in(113)ways.