Discrete Mathematics - Lecture 6.3 Combinations and Permutations PDF

Preview

Summary

Discrete Mathematics - Lecture 6.3 Combinations and Permutations...

Description

Math 3336 Section 6.3 Combinations and Permutations • • •

Permutations Combinations Combinatorial Proofs

Permutations Definition: A of a set of distinct objects is an objects. An ordered arrangement of r elements of a set is c Notation: The number of r-permutations of a set with n el Example: Let S = {1,2,3}.  The ordered  The ordered

e

rmutatio ermutati

Write all 2-permuta

Theorem: If ฀฀ is a positive integer and ฀฀ is an integer with 1 ≤ ฀฀ ≤ ฀฀, then there are r-permutations of a set with n distinct elements.

Page 1 of 6

Corollary 1: If ฀฀ and ฀฀ are integers with 1 ≤ ฀฀ ≤ ฀฀, then

Solving Counting Problems by Counting Permutations Example: How many ways are there to select a first-prize winner, a second prize winner, and a third-prize winner from 100 different people who have entered a contest?

g ABC?

Page 2 of 6

Combinations Definition: An n of elements o the set. Thus, an r-combination is simply a

d selection of r elements from r elements.

Notation: The number of r-combinations of a set with n distinct elements is denoted by The notation is also used and is called a binomial coefficient. (We will see the notation again in the binomial theorem in Section 6.4.) Example: Let S be the set {a, b, c, d}. Then {a, c, d} is a 3-combination from S. It is the same as {d, c, a} since the order listed does not matter. Find ฀฀(4,2).

Theorem: The number of r-combinations of a set with ฀฀ elements, where 0 ≤ ฀฀ ≤ ฀฀, equals

Page 3 of 6

Solving Counting Problems by Counting Combinations Example: How many poker hands of five cards can be dealt from a standard deck of 52 cards? Also, how many ways are there to select 47 cards from a deck of 52 cards?

Corollary: Let ฀฀ and ฀฀ be nonnegative integers with ฀฀ ≤ ฀฀. Then

Example: How many ways are there to select five players from a 10-member tennis team to make a trip to a match at another school?

Page 4 of 6

Example: A group of 30 people have been trained as astronauts to go on the first mission to Mars. How many ways are there to select a crew of six people to go on this mission?

Example: A judge has a jury pool of 40 people that contains 22 women and 18 men. She needs a jury of 12 people. a. How many juries can be made?

b. How many juries contain 6 women and 6 men?

Example: A club of 16 students, 7 juniors and 9 seniors, is forming a 5 member subcommittee. a. How many subcommittees can be made?

b. How many subcommittees contain 2 juniors and 3 seniors?

c. How many subcommittees contain all seniors?

d

Exam conta a

b

Page 6 of 6...