16 Probability and Distributions1.3.1 CountingRules..........................
We discuss three counting rules that are usually discussed in an elementary algebra
course.
Thefirstruleiscalledthemn-rule(mtimesn-rule), which is also called the
multiplication rule.LetA={x 1 ,x 2 ,...,xm}be a set ofmelements and let
B={y 1 ,y 2 ,...,yn}be a set ofnelements. Then there aremnordered pairs,
(xi,yj),i=1, 2 ,...,mandj=1, 2 ,...,n, of elements, the first fromAand the
second fromB. Informally, we often speak of ways, here. For example there are five
roads (ways) between cities I and II and there are ten roads (ways) between cities
II and III. Hence, there are 5∗10 = 50 ways to get from city I to city III by going
from city I to city II and then from city II to city III. This rule extends immediately
to more than two sets. For instance, suppose in a certain state that driver license
plates have the pattern of three letters followed by three numbers. Then there are
263 ∗ 103 possible license plates in this state.
Next, letAbe a set withnelements. Suppose we are interested ink-tuples
whose components are elements ofA. Then by the extendedmnrule, there are
n·n···n=nksuchk-tuples whose components are elements ofA. Next, suppose
k≤nand we are interested ink-tuples whose components are distinct (no repeats)
elements ofA.Therearenelements from which to choose for the first component,
n−1 for the second component, ...,n−(k−1) for thekth. Hence, by themnrule,
there aren(n−1)···(n−(k−1)) suchk-tuples with distinct elements. We call
each suchk-tuple apermutationand use the symbolPknto denote the number of
kpermutations taken from a set ofnelements. This number of permutations,Pkn
is our second counting rule. We can rewrite it as
Pkn=n(n−1)···(n−(k−1)) =n!
(n−k)!. (1.3.5)
Example 1.3.3(Birthday Problem).Suppose there arenpeople in a room. As-
sume thatn<365 and that the people are unrelated in any way. Find the proba-
bility of the eventAthat at least 2 people have the same birthday. For convenience,
assign the numbers 1 thoughnto the people in the room. Then usen-tuples to
denote the birthdays of the first person through thenthperson in the room. Using
themn-rule, there are 365npossible birthdayn-tuples for thesenpeople. This
is the number of elements in the sample space. Now assume that birthdays are
equilikely to occur on any of the 365 days. Hence, each of thesen-tuples has prob-
ability 365−n. Notice that the complement ofAis the event that all the birthdays
in the room are distinct; that is, the number ofn-tuples inAcisPn^365 .Thus,the
probability ofAis
P(A)=1−Pn^365
365 n.For instance, ifn=2thenP(A)=1−(365∗364)/(365^2 )=0.0027. This formula
is not easy to compute by hand. The following R function^4 computes theP(A)for
the inputnand it can be downloaded at the sites mentioned in the Preface.
(^4) An R primer for the course is found in Appendix B.