Intro to combinatorics, part 2: Combinations

Now that we’ve discussed the permutation, let’s meet its less-picky sibling, the combination.

Combinations are like permutations with one small difference: order does not matter. It’s like reaching into a bag of Skittles and picking out a handful: whether those pieces were the first you touched or the last, they’re all going to end up in your mouth.

Let’s pretend I’m running a lottery. I put 12 balls (lettered A through L) into a bag and pick 3 out at random. How many different ways of picking them are possible?

If the order mattered, as it would in a permutation, there would be

12P3	=	12!	=	12!	=	12 x 11 x 10 x 9!
		(12-3)!		9!		9!

or 1,320 possible permutations. (Note this is the same number as my horse-racing example from the previous post.)

But in this lottery, it doesn’t matter which ball comes out first, second, or third. Let’s say you buy a ticket with the letters D, F, and K. In how many different ways can those three balls come out to make you a winner?

D-F-K	F-D-K	K-D-F
D-K-F	F-K-D	K-F-D

There are 6 different permutations (ordered outcomes) involving the combination of D, F, and K. So, in a way, you are getting six permutations for the price of one. But then again, so is everyone else who’s playing the game.

Eliminating duplicates

Because some permutations are effectively the same as others in our lottery, our 1,320 number is too high. We have 6 times as many combinations as we originally counted. Six, you might notice, is equal to 3! – or k! in this example.

The number of ways you can choose a combination of k objects from a set of n objects is equal to:

nCk	=	n!
		k! x (n–k)!

The formula is almost the same as that for a permutation; we’re just including the part in yellow, which makes us account for the “identical” orders.

Therefore, in my lottery, there are

12C3	=	12!	=	12!	=	12 x 11 x 10 x 9!
		3! x (12-3)!		3! x 9!		6 x 9!

or 220 different possible combinations.

English is stupid

There’s an easy way to remember the distinction between permutations and combinations. What is this thing called?

We call it a combination lock. But since you have to give three consecutive numbers in order, it should really be called a permutation lock. Funny, huh?

Practice questions

Now, it’s time to see how well you’ve grasped this concept.

Question 1. I have 7 friends who need a ride, but I have room enough for only 4 in my car. (My friends don’t care where they sit, just that they get a spot.) How many different combinations of friends can I bring with me?

[spoiler]Since order (position) doesn’t matter, I have a combination of “7, choose 4”.

7C4	=	7!	=	7!	=	7 x 6 x 5 x 4!
		4! x (7-4)!		4! x 3!		4! x 6

There are 35 different possible combinations of friends I can pick to take with me.[/spoiler]

Question 2. In a Jeopardy! tournament, the 10 non-winning quarterfinalists are eligible for four wild-card slots. It doesn’t matter whether you’re the #1 wild card or the #4 wild card, you’ll get the same reward: a trip to the semifinals. Therefore, order does not matter.

How many different combinations of wild cards can be made from the set of non-winners? (Another way to think about this: if I put the non-winners’ names into a hat and pulled out four, how many different groups of four could I possibly get?)

[spoiler]This is another combination: I’m starting with 10, and choosing 4.

10C4	=	10!	=	10!	=	10 x 9 x 8 x 7 x 6!
		4! x (10-4)!		4! x 6!		4 x 3 x 2 x 1 x 6!

I can then cancel out the 8 on the top with the 4 x 2 on the bottom, and cancel out the 3 on the bottom using the 9 on top. I’m left with

10 x 9 x 8 x 7	=	10 x 93 x 7
4 x 3 x 2		3

meaning there are 210 possible combinations of wild cards from our 10 non-winners.[/spoiler]

In the next post: how I use combinatorics, probability, and a wealth of data from the J! Archive to derive optimal wagers in Jeopardy! tournaments.