Permutations, Combinations: How to Calculate Arrangements

The words “permutation” and “combination” may not seem different in the general lexicon, but in mathematics they mean two very different things.

The terms relate to how many ways you can arrange elements of a set. These kinds of problems range from the trivial to having real-world applicability and utility; examples include:

  • In a committee of 5 people, how many ways are there to reach a majority vote?
  • Given 5 ice cream flavors, how many two-scoop choices are there?
  • How many 4-letter arrangements can be made from a 10-letter word?
  • How many different lock combinations are there on an old locker padlock?
  • An ATM machine has 10 numeric keys; how many 4-digit PINs are possible?

(By the way, the first two describe combinations; the remaining three describe permutations…continue reading to learn why, and to see the solutions.)

Deciding which is applicable

First we need to understand how they are different, since the virtually interchangeable words seem synonymous to the layman. The mathematical difference between permutations and combinations is simple: if ordering is not significant, you are calculating combinations; if the order is relevant, you are calculating permutations.

In a committee of 5 people, how many ways are there to reach a majority vote?
This is a combination because the order of the votes is irrelevant, only the sum of the votes.

Given 5 ice cream flavors, how many two-scoop choices are there?
A cup of chocolate-vanilla is indistinguishable from a cup of vanilla-chocolate. Ordering is irrelevant, so you’re dealing with combinations.

How many 4-letter arrangements can be made from a 10-letter word?
This is a permutation because order does matter. Take the word “DIFFERENCE.” The arrangements “DIFF” and “DFIF” are completely distinct in this context.

How many different lock combinations are there on an old locker padlock?
The idea of having a “combination lock” is what makes this one tricky. That use of the word “combination” here is a red herring — the fact is, this device should be called a “permutation lock” because the order does indeed matter. If the lock opens with 32-16-25, it does not also open with 25-32-16. The order of the digits matters, so you’re dealing with permutations.

An ATM machine has 10 numeric keys; how many 4-digit PINs are possible?
Just like the lock above, PIN digit ordering is significant. The PIN “1234” is not equivalent to “4321”. This problem concerns permutations.

Solving Permutations

Given n objects selected r at a time, how many permutations are there?

The mathematical notation for the above is n_P_r, or Pn,r. The formula for the solution depends on the question of repetition: can an item be re-used?

If re-use / repetition is allowed, the formula is simply: Untitled.png

If re-use / repetition is forbidden, the formula becomes: Untitled.png

So, how many 4-letter arrangements can be made from a 10-letter word? The notation for this is 10_P_4, or P10,4. And because once you’ve used a letter it’s crossed of the list of eligible letters, repetition is disallowed. We use the second formula, and the solution is 10! / 6!, or 5,040.

How many different lock combinations are there on an old locker padlock? Let’s assume three digits, using a dial that goes from 1-36. The notation for this is 36_P_3, or P36,3. Repetition is allowed — it’d be perfectly legal to use the combination “18-25-18” — so the solution is simply 36 cubed, or 46,656.

An ATM machine has 10 numeric keys; how many 4-digit PINs are possible? The notation is 10_P_4, or P10,4. If the bank permits repetition of digits in your PIN, like “1115,” then the solution is 10 to the power of 4, or 10,000 different PIN possibilities. If the bank prohibits repetition of digits, the solution is smaller: 10! / 6!, or 5,040.

Solving Combinations

Given n objects selected r at a time, how many combinations are there?

The mathematical notation for the above is n_C_r, or Cn,r. The formula for the solution again depends on the question of repetition: can an item be re-used?

If re-use / repetition is allowed, the formula is: combinations-repeat.png

If re-use / repetition is disallowed, the formula is: combinations-no-repeat.png

Given 5 ice cream flavors, how many two-scoop choices are there?
Repetition is allowed here: a person could choose two scoops of chocolate if they wanted. The notation is 5_C_2, or C5,2. The solution is 15.

In a committee of 5 people, how many ways are there to reach a majority vote?
This is clearly a case of repetition being disallowed: a person can vote exactly once. And what’s more, there’s another layer of complexity here: how many ways a majority vote can be reached.

5 yes votes is one way.
4 yes votes is another way.
3 yes votes is the final way.

Each of these is a separate calculation, the total being: 1 + C5,4 + C5,3.

Simplified, that’s 1 + 5 + 10, or 16.

Advertisements

3 thoughts on “Permutations, Combinations: How to Calculate Arrangements

  1. Pingback: Combinations No Repeats | AllGraphicsOnline.com

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s