Unit 8

8.1 Counting Principles and Probability

The (Extended) Fundamental Counting Principle

If a first action can be performed in a ways, a second action in b ways, a third in c ways, . . . , and so on, then all of the actions can be performed together, in this order, in a × b × c × · · · ways.

Basic Methods of Counting

Method 1: Tree diagram

Method 2: Blanks, squares, boxes, etc.

Definition:  Permutation

A permutation is an ordered arrangement of elements from a given set.

For example, the permutations of the letters A, B , C, and D taken two distinct letters at a time are

AB   AC   AD

BA   BC   BD

CA   CB    CD

DA   DB    DC

Note that the order matters, so AB and BA are different arrangements.

Definition:  Combination

A Combination is an unordered selection of items taken from a given set.

For example, the combinations of the letters A, B , C, and D taken two distinct letters at a time are

AB   AC   AD   BC   BD   CD

8.2 Permutations – Ordered Arrangements

Theorem

The number of ways to arrange n distinct objects in order is n!.  Said another way, n Pn  = n!. The number of permutations of an n distinct element set is n!.

Note: 0! = 1

Permutations Summary

• If n objects are distinct, there are n! permutations of the objects. That is to say, there are n! ways of arranging them.

• If r objects are arranged from a group of n distinct objects there are n Pr  permutations of the objects. That is to say there are n Pr  ways of arranging the r objects, and

n!    

n Pr  = P(n,r) =

• If a collection of n elements is to be arranged and a elements are indistinguishable of one type, b elements are indistinguishable of a second type, c elements are indistinguishable of a third type, and so on, then the number of arrangements is

n!    

a!b!c! ···

The Birthday Problem

P(at least two people in a group of k people will share a birthday) = 1 − 

8.3 Combinations – Unordered Selections

The Number of Combinations Formula

The total number of combinations of n objects taken r at a time is equal to

n Cr  = r(n)  =

8.4 Binomial Models

A portion of the Pascal’s triangle is shown below. For example,  3(4)  is in row n = 4 and in

position r = 3.

Theorem:  Binomial Theorem

If n is a natural number, then the binomial expansion of (x + y)n  is given by

(x + y)n    = 0(n) xn + 1(n) xn − 1y + 2(n) xn −2y2 + ··· + r(n) xn −r yr + ··· + n(n) yn

Written in sigma notation:

(x + y)n  =  k(n) xn −k yk  =  k(n) xk yn −k

Example: In the expansion of (2x − 3)9  , determine the coefficient of term containing x3 .

Solution: The general term of the expansion of (a + b)n  is  r(n) an −r br .

Using a = 2x, b = −3, and n = 9:

r(n) an −r br  = r(9) (2x)9 −r ( −3)r

= r(9) (2)9 −r ( −3)r x9 −r

For the term containing x3 , we require 9 − r = 3:

9 − r = 3

r = 6

Therefore,

r(9) (2)9 −r ( −3)r x9 −r  = 6(9) (2)9 −6 ( −3)6 x9 −6

= (84)(8)(729)x3

= 489888x3

Therefore, the coefficient of term containing x3  is 489888.

A binomial experiment is a probability experiment that satisfies all of the following four requirements.

• The number of trials, called Bernoulli trials, is fixed;

• Each trial is independent of the other trials;

• There are only two outcomes (sometimes referred to as success or failure) with each trial; and

• The probability of each outcome remains constant from trial to trial.

As an example, tossing a coin five times and recording the number of heads is a binomial experiment.

• There are five trials.

• The coin has no ”memory,” so each flip of the coin is independent of the others.

• There are only two outcomes, heads or tails (with heads defined as a success).

• The probability of a head remains at  for every trial.

The binomial distribution is a discrete probability distribution of the number of successes in a series of n independent trials with each trial having two possible outcomes and a con- stant probability of success.

Definition:  Binomial Distribution

In general, the binomial distribution is given by

P(X = x) =   x(n) px qn −x    or P(X = x) = x(n) px (1 − p)n −x

where

• p is the numerical probability of a defined success,

• q is the numerical probability of a defined failure,

• n is the number of trials,

• x is the number of success in n trials, and

• X is the assigned random variable.

The expectation of the number of successes in a binomial distribution of n Bernoulli trials with probability p of success on each trial is

E(X) = np

Example:  A manufacturing company that makes a specific car component estimates that 0.1% of their products are defective. If a customer orders 25 of the components, what is the probability that at least one of the components is defective?

Solution: P(at least one is defective) = 1 − P(X = 0) = 1 −  0(25) (0.001)0 (0.999)25  ≈ 0.025