Combinations

THEOREM  The number of r-combinations of a set with n elements, where n is a non-negative integer and r is an integer with 0 ≤ r ≤ n, equals
C(n, r) = n!\r!(n − r)!

 

Here note that we are only counting unordered selections of objects..i.e ordered not matter

Example :Let S be the set {1, 2, 3, 4}. Then {1, 3, 4} is a 3-combination from S. (Note that {4, 1, 3} is the same 3-combination as {1, 3, 4}, because the order in which the elements of a set are listed does not matter.)

 

 

An r-combination of elements of a set is an unordered selection of r elements from the set. Thus, an r-combination is simply a subset of the set with r elements.

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 standard deck of 52 cards?

 

Solution: Because the order in which the five cards are dealt from a deck of 52 cards does not matter, there are C(52, 5) = 52! /5!47!

 

To select 47 cards from 52 cards we can write as,

C(52, 47) = 52! /47!5!

 

Note: Let n and r be nonnegative integers with r ≤ n. Then C(n, r) = C(n, n − r).

 

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?

Solution:

the number of 5-combinations of a set with 10 elements. By Theorem , the number of such combinations is C(10, 5) = 10! /5! 5! = 252.

 

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 (assuming that all crew members have the same job)?

 

Solution:

The number of ways to select a crew of six from the pool of 30 people is the number of 6-combinations of a set with 30 elements

C(30, 6) = 30!/ 6! 24! = 30 · 29 · 28 · 27 · 26 · 25 /6 · 5 · 4 · 3 · 2 · 1 = 593,775.

 

EXAMPLE  How many bit strings of length n contain exactly r 1s?

 

Solution:

The positions of r 1s in a bit string of length n form an r-combination of the set {1, 2, 3,...,n}. Hence, there are C(n, r) bit strings of length n that contain exactly r 1s.

 

EXAMPLE :

 Suppose that there are 9 faculty members in the mathematics department and 11 in the computer science department. How many ways are there to select a committee to develop a discrete mathematics course at a school if the committee is to consist of three faculty members from the mathematics department and four from the computer science department?

 

Solution: By the product rule, the answer is the product of the number of 3-combinations of a set with nine elements and the number of 4-combinations of a set with 11 elements. The number of ways to select the committee is

C(9, 3) · C(11, 4) = 9! /3!6! · 11! /4!7!

                                         = 84 · 330

                                            = 27,720.

 

0Comment