Put your knowledge to the test with the accompanying brain teasers  Day to day, we regularly encounter situations where we wish to quickly assess the number of distinct outcomes we should be concerned with. For example, every day we wake up and pick out an outfit before getting dressed and beginning our routines. We often intuitively recognise that there is a wide variety of options available to us, but many of us won't stop to contemplate the number of potential arrangements or outcomes of our decision making and how probable each one is.

A permutation is a specific arrangement (or ordering) of any set of distinct objects. We can determine how many permutations are possible of any set of objects fairly easily by contemplating the number of options we have in the process of arrangement.

For example, if you had a selection of 10 objects that you wanted to arrange into 10 positions, you would have 10 possible locations to place the first object. Once that object is placed, only nine locations remain to place the second object. Then only eight locations would remain to place the third, and so on until you had finally placed the tenth object in the only remaining spot. If we multiply the number of options we have at each stage, we obtain the total number of possible arrangements (permutations).

There are thus 3,628,800 possible permutations of 10 distinct objects if we are arranging all 10 of them. Sometimes, though, we are only arranging a selected subset of objects from within a larger group. For instance, we may wish to contemplate the number of ways to select people for specific roles from a pool of candidates.

Formally speaking, the number of permutations of r items selected from a collection of n distinct objects is given by

Where the ! sign denotes a factorial, which requires the multiplication of a value by all of the descending values to 1.

Political parties often have a group of candidates running for leadership positions, and from the same pool one president or prime minister will be selected while other candidates are slotted into cabinet positions. If there are 10 candidates running for four leadership positions, then there would be far less than 3 million possible permutations.

Because the arrangement stops after the four positions are filled, the number of possible selection orders is far lower.

Permutations should be applied to probabilities when we are worried about the order of events that are taking place. We simply divide the number of permutations of the outcomes we are concerned with by the number of possible arrangements in a given situation. ## Teaser #1

How many different five-character passwords are possible if the password must contain at least one English letter and one number between 0 and 9 (characters may repeat)? pocketfruity.com

Roll over to reveal answer

Answer: We can treat this situation as if three of the five characters can be selected from all 26 letters and 10 digits. That would be given by 36 x 36 x 36 (or 363). Then. for one spot we must pick a letter (26) and another spot we must pick a number (10). Lastly we must consider that once we have selected the eight characters, we must arrange them (5! arrangements are possible).

Thus 363 x 26 x 10 x 5 x 4 x 3 x 2 x 1 gives us 1,455,667,200 possible password combinations.

## From permutations to combinations

In many situations, specific orders are of no consequence to us and we are only worried about which objects are being selected. When arrangement, or order of selection, no longer becomes a concern, we are instead working with combinations. These situations will result in far smaller numbers of possible outcomes because we treat selections of specific groups of distinct objects as the same, irrespective of when they were picked.

For example, the distinct arrangements of ABC, ACB, BAC, BCA, CAB and CBA are all considered identical because the same three letters make up each group. Six permutations of the three selected letters would instead be viewed as a single combination.

If we were to explore the idea of three-letter arrangements for the entire alphabet, the distinction becomes more clear. When order matters, there are 26 x 25 x 24 = 15,600 three letter permutations of the English alphabet. Because every three-letter combination can be arranged 3 x 2 x 1 = 6 ways, the number of distinct combinations is actually only 15,600 / 6 = 2,600. Essentially the number of distinct combinations of r objects selected from a pool of n available items is just the number of permutations divided by the number of ways we can arrange the objects that have been selected.

## Combinations in card games

If you are playing a card game such as poker, combinations of cards that come up are likely more relevant to individual players than the order in which they do so. Lotteries, on the other hand, tend to require the winning numbers to be in a specific order, and would thus be a situation requiring permutations to analyse.

The powerful nature of combinations lets us answer some challenging questions fairly easily. Consider a game of Texas Hold ‘Em poker where you are confident in your hand but are also concerned about the cards that may be dealt on the flop. For the sake of argument, let us consider the situation where you have a straight—but what about the probability of one of your opponents having a flush? We apply combinations rather than permutations because the order in which cards are presented is irrelevant when constructing a winning hand.

Let’s assume you have a 9 of diamonds and a 7 of clubs. The flop contains a 5 of diamonds, along with a 6 and 8 of hearts. If any of your opponents has a heart, you may be worried about the probability of two more hearts coming up, because a flush will defeat your straight. First we can assess the probability that one of your opponents has a heart in their pocket. We do this by subtracting the probability of none of them being dealt a heart from 100%.

Your opponents have a selection of six cards between them. There are 36 non-hearts remaining, and 47 cards you don’t know the identity of. If none of your opponents had a heart in their pocket, then we would be dealing with the permutations of six cards taken from the 36 non-hearts divided by all of the possible arrangements of six cards selected from the pool of 47 available to be dealt.

So there is an 82% chance that at least one of your three opponents has a heart in their pocket.

Now we are concerned with the probability of two hearts being dealt to complete the hand. There are 41 cards that have not been dealt yet. Depending on how many hearts your opponents have, there are between 5 and 11 available still in the deck. We are only concerned about this if one of your opponents was dealt a heart, so we actually only need to worry about a maximum of 10 available hearts in the deck.

Thus the probability of your opponents having one or more hearts, and then seeing two hearts dealt on the turn and the river is simply the product of these two probabilities, 82% x 5.5% = 4.5%. The 5.5% probability will also decline if more than one of your opponents has a single heart dealt to them, because there are fewer undealt hearts remaining in the deck. ## Teaser #2

How many different arrangements are possible of the letters in MISSISSIPPI? pocketfruity.com

Roll over to reveal answer

Answer: The word has 11 letters but a number of them are identical. We deal with this by dividing the number of distinct arrangements by the number of repetitions of each identical letter.

11! will give the number of possible arrangements of the letters, and we then need to divide by 4! for the I’s, 4! for the S’s and 2! for the P’s. This results in 11! / (4! * 4! * 2!) = 34,650.

## When to apply permutations vs. combinations

Whether we decide to analyse a specific situation with permutations and combinations hinges entirely upon whether or not we are worried about the order of arrangement. Ordered lists, selection of individual items for specific slots, or roles will require permutations. If you are only selecting groups of items and ordering is irrelevant, then you should be analysing the situation using combinations.

Examples of situations requiring the two types of analysis:

## Permutations

Phone numbers; passwords; addresses; postal codes; license plates; USBN or ISBN codes; elections; rankings; appointments

## Combinations

Party invitations; picking teams (irrespective of position); shopping; course timetabling

Lastly, we can explore another probability question that is interesting whenever you get a group of people together. It often strikes people as unusual whenever they encounter someone with the same birthday. This makes sense superficially because the probability of any individual person having the same birthday as you is 4 in 1461, or 1 in 365.25 (the 0.25 is required if we are accounting for leap years).

Interestingly, if we bring together a group of people, the probability of any two of them having the same birthdate will increase drastically. We can show this mathematically by contemplating the probability of no two people in a group sharing the same birthdate, and subtracting this result from one. For the sake of argument, we will work with a 365-day year rather than the more accurate situation involving leap years.

We use permutations of group size n selected from the 365 possible dates for all birthdays, because we are subtracting the situation where no two birthdays are the same.

Here the denominator (number of possible outcomes) is 365n because everyone in the group could have their birthday on any of the 365 possible dates. As the number of people in the group, n, increases in size, the probability (P(A)) of two sharing a birthday will rise quickly.

So if you’re ever at a gathering of 35 or more people, you know there is a better than 80% chance that two of them were born on the same day of the year.

Permutations and combinations allow us to explore a wide variety of counting and probability problems with relative ease. Adding up the number of possible outcomes in many situations is prohibitive and time consuming, but this handy series of shortcuts can simplify the process entailed considerably. ## Teaser #3

Ten identical playing pieces are placed on a 5x5 game board. How many ways could the 10 pieces be placed if there are no restrictions? How many ways could the 10 pieces be placed if there must be two pieces in each row? pocketfruity.com

Roll over to reveal answer

Answer: There are 25 locations and we are placing 10 objects in various positions. Because the objects are identical it doesn’t matter which object goes where, so we would find 25C10 = 3,268,760 distinct positional arrangements for the 10 playing pieces.

If we have to place two pieces in each of the five rows, we would have 5C2 = 10 possible arrangements for each row. Thus there would be 10 x 10 x 10 x 10 x 10 = 100,000 possible arrangements for the entire board. 