Combinations, and their younger siblings Permutations, come up frequently when analyzing game designs and strategies. These concepts are also frequently taught and explained poorly, as in “here, use this formula to solve that problem”. In this blog we’ll investigate the mathematics behind counting combinations, and see how it can be used to determine the odds of drawing specific cards in the deck building game Ascension. If you’re not familiar with this game, there is a great implementation for iOS devices.

In Ascension, each player starts with their own deck of ten cards. Before each turn they randomly draw five cards from their own deck. Eight of the cards in each starting deck are called Apprentices (A), and the other two are Militia (M). Different combinations of Apprentices and Militia may make more or less useful starting hands depending on a separate center row. So we’re going to figure out how likely different starting hand advantages might be in this game.

We’ll begin by considering the different ways that a deck of ten cards can be arranged after shuffling (another name for each possible arrangement is a permutation). There are ten different cards that could end up on the top of the deck after shuffling. With each of those possible deck tops, there are nine other cards that might follow. So there are a total of 10 * 9 = 90 different possibilities for the top two cards in a shuffled ten card deck. Notice how this differs from the number of ways you might roll two ten-sided dice (10*10=100): since each card can only occupy one position in the deck, but every value can be rolled on every die. Each of our 90 possibilities might be followed by any the 8 remaining cards, and so on. The name for the mathematical operation of multiplying every number from a starting value down to one is factorial, and it is typically expressed with an exclamation mark. We can use this operation to calculate the number of ways that a deck of ten cards can be shuffled.

	10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3,628,800

That’s a lot of permutations, but many of them are redundant for our purposes. For instance, imagine swapping the first two cards from any of these possible orderings. This will result in a new permutation (aka ordering), but it will not change which cards we draw in our first hand.

So how can we reduce these 3.6 Million+ permutations down to the number of orderings that result in unique starting hands? We divide out the redundancies. We need to figure out how many different permutations there are for each unique starting hand, and then divide our 3.6 Million by that number. We’ll start by calculating the number of ways that any five cards can be arranged within the top five positions of the deck. Notice that this is similar to the problem of calculating the number of ways the entire deck can be shuffled, but with only five cards instead of ten.

	5! = 5 * 4 * 3 * 2 * 1 = 120

It’s tempting to divide by 120 and think we’re done. But for each of these 120 ways that five cards can be arranged at the top of a starting deck, the bottom five cards can also be arranged in just as many ways. So there are a total of 120 * 120 = 14,400 different ways that a deck of ten cards can be rearranged without changing which five cards are on the top and bottom of the deck. Dividing our initial 3.6 Million+ permutations for a shuffled deck by this 14,400 will tell us the number of unique starting hands we might draw from a deck of ten cards.

	10! / (5! * 5!) = 3,628,800 / 14,400 = 252

It’s possible that you recognize these calculations from the general formula for combinations.

	n C k = n! / (k! * (n-k)!)

The left hand side of this equations just states that this is the formula for calculating the number of ways that you can choose k objects from a set of n objects (the C stands for combinations and choose). In our case, we are finding the number of ways to choose k=5 cards from a set of n=10 cards. To calculate this, we started with the number of ways all n=10 cards could be arranged: n!. We then divided out the redundant ways that the first k=5 cards that we are drawing could be ordered: k!, and then finally divided out the ways that the remaining n-k=5 cards at the bottom of the deck might be arranged: (n-k)!.

Back to our Ascension example. We know that there are 252 unique ways to draw five cards from a shuffled deck of ten. But in Ascension, 8 of these cards are Apprentices and the other 2 are Militia. So if we only consider the types of cards that we draw (rather than which of those cards we draw), there are really just three types of opening hands we might draw. The likelihood of each opening is the percentage of hands, out of the 252 possible, that match that opening’s pattern.

	Opening:	 #1	 #2	 #3
	Probability:	?/252	?/252	?/252

Consider the number of ways that you can draw five apprentices in your first hand. There are eight apprentices total, so finding the number of ways you can draw five of them can be formulated as a combinations problem: 8 C 5.

	8 C 5 = 8! /(5! * (8-5)!) = 40,320 / 720 = 56

So the probability of drawing Opening #1 is 56/252. This is also the probability for Opening #3, because there are the same number of ways to select five cards for the top of the deck, as there are ways to select five cards for the bottom of the deck. All that’s left is to calculate the number of ways that we might draw the hands in Opening #2. This involves choosing four of the eight Apprentices, and one of the two Militia. Each way of selecting Apprentices can occur with each way of selecting the Militia, so we should multiply the the two combinations: (8 C 4) * (2 C 1)

	8 C 4 = 8! / (4! * (8-4)!) = 40,320 / 576 = 70
	2 C 1 = 2! / (1! * (2-1)!) = 2 / 1 = 2
	(8 C 4) * (2 C 1) = 70 * 2 = 140

This helps us complete our probability table with a 140/252 chance of drawing Opening #2.

	Opening:	 #1	 #2	 #3
	Probability:	22.2%	55.5%	22.2%

I originally intended to take this example a bit further, but don’t want this post to get too long (if it isn’t already). As food for thought, you might consider further calculating how often each of these openings should coincide with valuable starting center row cards that require four or five Apprentices to be purchased. As always, please let me know what you think of this series, and whether you have any questions or comments that might help improve it going forward.

Leave a Comment

Related Posts

Tuesday, January 24th, 2012