Section 13-2

Factorials, Permutations, and Combinations

FACTORIALS

How many different ways are there for a group of n people to get in a single-file line?

We'll start by listing all of them for small values of n. There is obviously only one way for one person (named "A") to line up:

A

There are two ways for two people (A and B) to line up:

AB, BA

There are six ways for three people to line up:

ABC, ACB, BAC, BCA, CAB, CBA

And there are 24 ways for four people to line up:

ABCD ABDC ACBD ACDB ADBC ADCB

BACD BADC BCAD BCDA BDAC BDCA

CABD CADB CBAD CBDA CDAB CDBA

DABC DACB DBAC DBCA DCAB DCBA

This last table should give you an idea of the pattern. For each person in front, there are six ways to line up the three people behind them. So, for five people, there are 24 × 5 = 120 different orders.

We can write this as:

120 = 5 × 4 × 3 × 2 × 1

In general, the number of different ways to line up a group of n people is:

n × (n - 1) × (n - 2) × · · · × 2 × 1

There is a shorthand notation for this: n! (pronounced n factorial).

PERMUTATIONS

Given a group of n objects, how many ways are there to line up some subgroup of m of them?

For example, suppose you're a television programmer, and you have five half-hour shows to choose from, but only three time slots. How many different programs are possible?

If we name the shows A, B, C, D, and E, we get:

ABC ABD ABE ACB ACD ACE ADB ADC ADE AEB AEC AED

BAC BAD BAE BCA BCD BCE BDA BDC BDE BAC BAD BAE

CAB CAD CAE CBA CBD CBE CDA CDB CDE CEA CEB CED

DAB DAC DAE DBA DBC DBE DCA DCB DCE DEA DEB DEC

EAB EAC EAD EBA EBC EBD ECA ECB ECD EDA EDB EDC

In this case, there are 5 choices for the first program, 4 choices for the second program, and 3 choices for the last program. So the answer is:

5 × 4 × 3 = 60

If there were 8 programs and 4 time slots, we would have:

8 × 7 × 6 × 5 = 1680

In general, the number of possible arrangements of m objects from a set of n is given by:

_nP_m = n × (n - 1) × (n - 2) × · · · × (n - m + 1)

COMBINATIONS

In the above example, the order of the programs mattered: ABC was counted seperately from ACB.

Sometimes, order doesn't matter. For example, you might be asked how many possible groups of three can be made from a set of five individuals. Here, groups ABC, ACB, BCA, BAC, CAB, and CBA are all the same group of three people.

The trick here is to do the permutation problem, but to divide out by the number of different orders for each group. In this case:

In general, if you want to find the number of groups of m individuals that can be selected from a set of n, first find _nP_m and then divide by m!.