<< Chapter < Page Chapter >> Page >

Forming word sequences is an example of permutations, while forming committees is an example of combinations – the topic of this section.

Permutations are those arrangements where order is important, while combinations are those arrangements where order is not significant. From now on, this is how we will tell permutations and combinations apart.

In [link] , there were six permutations, but only three combinations.

Just as the symbol n Pr size 12{n"Pr"} {} represents the number of permutations of n size 12{n} {} objects taken r size 12{r} {} at a time, nCr size 12{ ital "nCr"} {} represents the number of combinations of n size 12{n} {} objects taken r size 12{r} {} at a time.

So in [link] , 3P2 = 6 size 12{3P2=6} {} , and 3C2 = 3 size 12{3C2=3} {} .

Our next goal is to determine the relationship between the number of combinations and the number of permutations in a given situation.

In [link] , if we knew that there were three combinations, we could have found the number of permutations by multiplying this number by 2 ! size 12{2!} {} . That is because each combination consists of two letters, and that makes 2 ! size 12{2!} {} permutations.

Given the set of letters A , B , C , D size 12{ left lbrace A,B,C,D right rbrace } {} . Write the number of combinations of three letters, and then from these combinations determine the number of permutations.

We have the following four combinations.

ABC BCD CDA BDA

Since every combination has three letters, there are 3 ! size 12{3!} {} permutations for every combination. We list them below.

ABC BCD CDA BDA

ACB BDC CAD BAD

BAC CDB DAC DAB

BCA CBD DCA DBA

CAB DCB ACD ADB

CBA DBC ADC ABD

The number of permutations are 3 ! size 12{3!} {} times the number of combinations. That is

4p3 = 3 ! 4C3 size 12{4p3=3! cdot 4C3} {}

or 4C3 = 4P3 3 ! size 12{4C3= { {4P3} over {3!} } } {}

In general, nCr = n Pr r ! size 12{ ital "nCr"= { {n"Pr"} over {r!} } } {}

Since n Pr = n ! n r ! size 12{n"Pr"= { {n!} over { left (n - r right )!} } } {}

We have, nCr = n ! n r ! r ! size 12{ ital "nCr"= { {n!} over { left (n - r right )!r!} } } {}

Got questions? Get instant answers now!
Got questions? Get instant answers now!

Summarizing,

  1. Combinations

    A combination of a set of elements is an arrangement where each element is used once, and order is not important.

  2. The Number of Combinations of n size 12{n} {} Objects Taken r size 12{r} {} at a Time

    nCr = n ! n r ! r ! size 12{ ital "nCr"= { {n!} over { left (n - r right )!r!} } } {}

    Where n size 12{n} {} and r size 12{r} {} are natural numbers.

Got questions? Get instant answers now!

Compute:

  1. 5C3 size 12{5C3} {}
  2. 7C3 size 12{7C3} {} .

We use the above formula.

5C3 = 5 ! 5 3 ! 3 ! = 5 ! 2 ! 3 ! = 10 size 12{5C3= { {5!} over { left (5 - 3 right )!3!} } = { {5!} over {2!3!} } ="10"} {}
7C3 = 7 ! 7 3 ! 3 ! = 7 ! 4 ! 3 ! = 35 size 12{7C3= { {7!} over { left (7 - 3 right )!3!} } = { {7!} over {4!3!} } ="35"} {} .
Got questions? Get instant answers now!
Got questions? Get instant answers now!

In how many different ways can a student select to answer five questions from a test that has seven questions, if the order of the selection is not important?

Since the order is not important, it is a combination problem, and the answer is

7C5 = 21 size 12{7C5="21"} {} .

Got questions? Get instant answers now!
Got questions? Get instant answers now!

How many line segments can be drawn by connecting any two of the six points that lie on the circumference of a circle?

Since the line that goes from point A size 12{A} {} to point B size 12{B} {} is same as the one that goes from B size 12{B} {} to A size 12{A} {} , this is a combination problem.

It is a combination of 6 objects taken 2 at a time. Therefore, the answer is

6C2 = 6 ! 4 ! 2 ! = 15 size 12{6C2= { {6!} over {4!2!} } ="15"} {}
Got questions? Get instant answers now!
Got questions? Get instant answers now!

There are ten people at a party. If they all shake hands, how many hand-shakes are possible?

Note that between any two people there is only one hand shake. Therefore, we have

10 C2 = 45   hand-shakes . size 12{"10"C2="45"" hand-shakes" "." } {}
Got questions? Get instant answers now!
Got questions? Get instant answers now!

The shopping area of a town is in the shape of square that is 5 blocks by 5 blocks. How many different routes can a taxi driver take to go from one corner of the shopping area to the opposite cater-corner?

Let us suppose the taxi driver drives from the point A size 12{A} {} , the lower left hand corner, to the point B size 12{B} {} , the upper right hand corner as shown in the figure below.

 This grid shows how a taxi driver must get from point A to point B.

To reach his destination, he has to travel ten blocks; five horizontal, and five vertical. So if out of the ten blocks he chooses any five horizontal, the other five will have to be the vertical blocks, and vice versa. Therefore, all he has to do is to choose 5 out of ten.

The answer is 10C5, or 252.

Alternately, the problem can be solved by permutations with similar elements.

The taxi driver's route consists of five horizontal and five vertical blocks. If we call a horizontal block H size 12{H} {} , and a vertical block a V size 12{V} {} , then one possible route may be as follows.

HHHHHVVVVV size 12{ ital "HHHHHVVVVV"} {}

Clearly there are 10 ! 5 ! 5 ! = 252  permutations size 12{ { {"10"!} over {5!5!} } ="252"" permutations"} {} .

Further note that by definition 10 C5 = 10 ! 5 ! 5 ! size 12{"10"C5= { {"10"!} over {5!5!} } } {} .

Got questions? Get instant answers now!
Got questions? Get instant answers now!

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Applied finite mathematics. OpenStax CNX. Jul 16, 2011 Download for free at http://cnx.org/content/col10613/1.5
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Applied finite mathematics' conversation and receive update notifications?

Ask