Properties of Relations III

CmSc 180 Discrete Mathematics

Counting and probability

Probability of an event

Consider an experiment that may have different outcomes. We are interested to know what is the probability of a particular set of outcomes.

Definition: Sample space S: all possible outcomes

Definition: Event – any subset of S

Definition: probability(Event) = (number of outcomes in E)/ (total number of outcomes)

Examples:

a)coins: What is the probability of having “heads” when tossing a coin?

b)Dice: What is the probability of having 6 when rolling a die?

Counting elements in a list

Suppose the chapter you have to read starts on p.5 and ends on p.10. How many pages do you have to read?

Rule: If m and n are integers and m ≤ n, there are n – m + 1 integers from m to n inclusive

Counting Cartesian products

Suppose we want to take a trip.We can go to Florida, California, or New York CityWe can drive or fly.How many different ``packages'' can we choose from?

Product rule:

Ordered sequences a1 a2 a3 ….an , ai Ai, the number of elements of Ai is Ni,

Number of ordered sequences is: N1 * N2 *N3 * …. Nn

The set of all ordered sequences is the Cartesian product of the sets Ai

Examples:

What is the probability to have 2 heads when tossing two coins?

What is the probability to have exactly one head?

What is the probability to have equal sides when rolling two dice?

Counting permutations

Permutations: sequences of elements of a given set, each element can occur only once.

Permutations of n elements = n!

Permutations of k elements out of n elements: P(n,k)=(n!)/ ((n-k)!)

Explanation: The first element can be chosen in n different ways. Once chosen, the second element can be chosen among (n-1) elements. Thus two elements can be chosen in n(n-1) way.

The choices for the third element are among n-2 element. At the end, the choice for the

k-th element is made among n-k+1 elements.

Hence the number of permutations is n(n-1)(n-2)….(n-k+1) = (n!)/(n-k)!

Counting combinations

Combinations: A combination is a selection of objects without regard to order. So combinations differ from permutations where order is taken into account.

The number of combinations of k elements out of n elements

C(n,k) is P(n,k) / (k!) = (n!) / ((k!)(n-k)!)

Problems:

1. Let A={a,b,c,d}

a. Compute the number of permutations of three elements of A.

b. Compute the number of combinations of three elements of A.

2. In how many was can we select a chairperson, vice-chairperson and a recorder from a group of 11 persons?

3. In how many ways can we select a committee of three from a group of 11 persons?

In exercises 4-8 refer to a club consisting of 6 men and 7 women.

4. In how many ways can we select a committee of three men and four women?

5. In how many ways can we select a committee of four persons that has at least one woman?

6. In how many ways can we select a committee of four persons that has at most one man?

7. In how many ways can we select a committee of four persons that has persons of both sexes?

8. In how many was can we select a committee of four persons so that Mabel and Ralph do not server together?

9. In how many ways can we select a committee of four Republicans, three Democrats and two Independents from a group of 10 Republicans, 12 Democrats, and four Independents?

10. How many eight-bit strings of 0's and 1's contain exactly three 0's?

11. How may eight-bit strings of 0's and 1's contain three 0's in a row and five ones?

In exercises 12-20 find the number of 5 card hands from a standard deck of 52 cards that satisfy the given conditions.

12. Containing all spades

13. All of the same suit

14. Containing cards of exactly two suits

15. Containing cards of all suits

16. Containing an Ace, 2, 3, 4 and 5 all of the same suit.

17. Consecutive and of the same suit. (assuming ace is the lowest card)

18. Consecutive (assuming ace is the lowest)

19. Containing three of one kind and two of another kind. (full house)

20. Containing two of one kind, two of a second kind and one of a third kind.

In exercises 21-24 a coin is flipped 10 times.

21. How many outcomes are possible?

22. How many outcomes have exactly three heads?

23. How many outcomes have at most three heads?

24. How many outcomes have a head on the fifth toss?