Iβve always confused βpermutationβ and βcombinationβ β which oneβs which?

Hereβs an easy way to remember: **permutation sounds complicated**, doesnβt it? And it is. With permutations, every little detail matters. Alice, Bob and Charlie is different from Charlie, Bob and Alice (insert your friendsβ names here).

Combinations, on the other hand, are pretty easy going. The details donβt matter. Alice, Bob and Charlie is the same as Charlie, Bob and Alice.

**Permutations are for lists (order matters) and combinations are for groups (order doesnβt matter).**

A joke: A "combination lock" should really be called a "permutation lock". The order you put the numbers in matters. (A true "combination lock" would accept both 10-17-23 and 23-17-10 as correct.)

## Permutations: The hairy details

Letβs start with permutations, or **all possible ways** of doing something. Weβre using the fancy-pants term βpermutationβ, so weβre going to care about every last detail, including the order of each item. Letβs say we have 8 people:

```
1: Alice
2: Bob
3: Charlie
4: David
5: Eve
6: Frank
7: George
8: Horatio
```

How many ways can we award a 1st, 2nd and 3rd place prize among eight contestants? (Gold / Silver / Bronze)

Weβre going to use permutations since the order we hand out these medals matters. Hereβs how it breaks down:

- Gold medal: 8 choices: A B C D E F G H (Clever how I made the names match up with letters, eh?). Letβs say A wins the Gold.
- Silver medal: 7 choices: B C D E F G H. Letβs say B wins the silver.
- Bronze medal: 6 choices: C D E F G H. Letβs sayβ¦ C wins the bronze.

We picked certain people to win, but the details donβt matter: we had 8 choices at first, then 7, then 6. The total number of options was 8 · 7 · 6 = 336.

Letβs look at the details. We had to order 3 people out of 8. To do this, we started with all options (8) then took them away one at a time (7, then 6) until we ran out of medals.

We know the factorial is:

Unfortunately, that does too much! We only want 8 · 7 · 6. How can we βstopβ the factorial at 5?

This is where permutations get cool: notice how we want to get rid of 5 · 4 · 3 · 2 · 1. Whatβs another name for this? 5 factorial!

So, if we do 8!/5! we get:

And why did we use the number 5? Because it was left over after we picked 3 medals from 8. So, a better way to write this would be:

where 8!/(8-3)! is just a fancy way of saying βUse the first 3 numbers of 8!β. If we have **n** items total and want to pick **k** in a certain order, we get:

And this is the fancy permutation formula: You have **n** items and want to find the number of ways **k** items can be ordered:

## Combinations, Ho!

Combinations are easy going. Order doesnβt matter. You can mix it up and it looks the same. Letβs say Iβm a cheapskate and canβt afford separate Gold, Silver and Bronze medals. In fact, I can only afford empty tin cans.

How many ways can I give 3 tin cans to 8 people?

Well, in this case, the order we pick people doesnβt matter. If I give a can to Alice, Bob and then Charlie, itβs the same as giving to Charlie, Alice and then Bob. Either way, theyβre equally disappointed.

This raises an interesting point β weβve got some redundancies here. Alice Bob Charlie = Charlie Bob Alice. For a moment, letβs just figure out how many ways we can rearrange 3 people.

Well, we have 3 choices for the first person, 2 for the second, and only 1 for the last. So we have 3 · 2 · 1 ways to re-arrange 3 people.

Wait a minuteβ¦ this is looking a bit like a permutation! You tricked me!

Indeed I did. If you have N people and you want to know how many arrangements there are for **all** of them, itβs just N factorial or N!

So, if we have 3 tin cans to give away, there are 3! or 6 variations for every choice we pick. If we want to figure out how many combinations we have, we just **create all the permutations and divide by all the redundancies**. In our case, we get 336 permutations (from above), and we divide by the 6 redundancies for each permutation and get 336/6 = 56.

The general formula is

which means βFind all the ways to pick k people from n, and divide by the k! variantsβ. Writing this out, we get our **combination formula**, or the number of ways to combine k items from a set of n:

## A few examples

Hereβs a few examples of combinations (order doesnβt matter) from permutations (order matters).

Combination: Picking a team of 3 people from a group of 10. C(10,3) = 10!/(7! · 3!) = 10 · 9 · 8 / (3 · 2 · 1) = 120.

Permutation: Picking a President, VP and Waterboy from a group of 10. P(10,3) = 10!/7! = 10 · 9 · 8 = 720.

Combination: Choosing 3 desserts from a menu of 10. C(10,3) = 120.

Permutation: Listing your 3 favorite desserts, in order, from a menu of 10. P(10,3) = 720.

Donβt memorize the formulas, understand why they work. **Combinations sound simpler than permutations, and they are. You have fewer combinations than permutations.**

## Leave a Reply

1109 Comments on "Easy Permutations and Combinations"

[…] (Brush up on combinations and permuations if you like). […]

Thanks alot! This was actally a better explanation then my teacher could give us =]

Awesome! Glad you found it useful π

finally this makes sense

this is an awesome site!

Thanks a million! It makes sense now!

Thanks for the comments, glad you found it useful.

If my chances are 1 in 13 million of winning the lottery and I buy 10 tickets, do my chances increase?

Hi D, when you buy multiple tickets you would add up the chances. So 10 tickets would be 1/13,000,000 + 1/13,000,000 + 1/13,000,000 … = 10 / 13,000,000

So buying multiple tickets would increase your chances for that particular lottery. If you somehow bought half of the available tickets, you’d have a 50-50 chance. And if you bought all of the tickets you’d win :).

Im not really sure but I dont think Kalid cares after nearly 9 years

WTF

WTF 2

WTF 3 …. DOTA 3 Confirmed

I’m having a stupid moment. I have a problem: how many combinations exist when one needs to select a team of 22 players from a squad of 40 players?

IS this 40!/22!(18!) = 113,380,261,800?

It seems a rediculaously large number! Please help me!

Hi David, yep, you got the formula right. The number of permutations (ways to order 22 people of 40) is:

40 * 39 * 38 … * 24 * 23 * 22 * 21 * 20 * 19 = 40! / 18!

[Be careful of off-by-one errors, I had a mistake at first. 40 to 19 is 22 people (just like 40 to 39 is 2 people, even though 40-39 is 1)]

And the number of ways to re-arrange 22 people = 22!

So we divide the first by the second and get

40!/18!(22!) = 113,380,261,800

113 billion does seem huge, but there’s a lot of multiplications happening. There’s 56 ways to pick 3 people from 8, which seems pretty large as well.

It’s one of those things where human beings (all of us!) aren’t great at intuitively estimating the impact of exponential growth. The birthday paradox and the effect of compound interest are other examples of this. I think it’s because we don’t encounter such mind-boggling growth or large numbers in a way we can really experience (at a certain point, millions, billions, and trillions become “a lot”, even though a trillion is a *million* times bigger than a million).

This helped with my question… sort of

Great Stuff! You should write a book!

Thanks for the encouragement Aaron! Once I have enough posts I would love to turn it into a book π

it was really useful dude!!!

thnx a lot!!!

No problem, glad it helped!

I play in a fantasy footfall league. I can select players for my team and they each earn points based on their performance in each weeks actual football game. I compete against other teams owners in my league and the owner with the most points each week wins. Also the points earned each week are totaled at the end of the year and the owner with the most points wins the annual point competition.

Of course there are limitations and rules to the game. Of all the players listed I may select only 22 players. Of the 22 players the team must be composed of:

3 quarterbacks (QB)(58 QBs)

6 running backs (RB)(81 RBs)

6wide receivers (WR)(125WRs)

2 tight ends (TE)(56 TEs)

3 kickers (K)(37Ks)

2 defenses (D)(32Ds)

Also each player is assigned a salary and my salary limit for the team is $60,000,000.00 for all 22 players.

I can trade for additional players each week but Iβm limited to 120 trades for the year.

Here is the question?:

??? Of all the players available which ;

2QB+6RB+6WR+2TE+3K+2D whose total salary does not exceed $60,000,000 will generate the most projected points?????

The program should list the top 20 combinations in descendinding order of points.

Attached is a file that lists all players available. Of all the columns available the only ones used will be Name (player), Salary (in thousands) and PNTS ( projected points for the in todays game).

I think your program PermutCombine will do some of the work but Iβ

Thanks again for your interest. Sam Eismont

if a train has 18 cars , and 3types of cargo must be transported, how many ways can the 3 types be transported if one type of cargo can at most occupy only ten cars per train?

Thanks alot!!!!

am studying n i have an exam 2mmorow !!

thnx 4 helpn me

Hi Besho, I’m glad I was abble to help!

10 pairs of shoes are well mixed up.4 shoes are randomly picked. What is the probablity of getting at least 1 complete pair

This is really an excellent way of explaining the things!!!

Hi Pras, thanks for the comment!

@Sahil: It’s a good question, but I want to make sure I’m not doing someone’s homework for them :).

In general, it’s easier to find the chance of “zero matches” and subtract this from 1, vs. finding the chance for 1 match.

So let’s find the chance for zero matches. Imagine picking your first shoe, A: nothing special here, you aren’t going get the match on a single shoe.

You pick shoe B: You have a 18/19 chance of getting zero matches (only A’s partner would match, of the 19).

You pick shoe C: You have a 16/18 chance of zero matches (only A and B’s partner would match, of the remaining 18).

You pick shoe D: You have a 14/17 chance of not getting any matches (only A and B and C’s partner would match, of the remaining 17).

If you multiply these chances you get the total chance for zero matches. Subtract from zero to get the chance for any match. At least I think that’s how it goes π

hey

I was about to crazy solving this sum which i now find was actually so simple thanks π

I feel the answer to this is simple but i am just not able to get it..

In an examination there are three multiple choice questions and each question has 4 choices. The number of sequences in which a student can fail to get all answers correct is..

Hi Safa, for that question it helps to take it one step at a time.

In a test with only 1 question, how many ways can you be wrong? 3. (Suppose the right answer is D… you could answer A, B or C).

Now how about 2 questions? Well, you have 3 ways to get the first question wrong, and another 3 ways to get the second one wrong. So the total is 3 * 3 = 9. (Let’s say the right answer is D and D. Then AA AB AB BA BB BC CA CB CC are all wrong).

Similarly, if you have 3 questions, then there is 3 * 3 * 3 = 3^3 = 27 ways to get all answers wrong. (You can write it out but will take a while: AAA AAB AAC ABA ABB ABC ACA ACB ACC… you get the idea π )

Hope this makes sense,

-Kalid