This post was updated in 2024 for the new GMAT.
First, a few practice questions. Remember — no calculator!
1) A radio station has to choose three days of the seven in a week to broadcast a certain program, and that set will repeat each week. The program can be broadcast equally on any of the seven weekdays —- weekdays vs. weekends don’t matter at all —- nor does it matter whether the days the program airs are adjacent or not. Absolutely any three of the seven weekdays can be chosen. How many different three-day combinations of the seven weekdays can be constructed?
-
(A) 9
(B) 15
(C) 21
(D) 35
(E) 56
2) Claudia can choose any two of four different candles and any 8 of 9 different flowers for a centerpiece arrangement. Given these choices, how many candle + flower groupings can she select?
-
(A) 54
(B) 72
(C) 96
(D) 144
(E) 432
3) A newly-wed couple is using a website to design an eBook Wedding Album to distribute to their friends and families. The template they have chosen has places for 3 large photos and 19 smaller photos. The couple has 6 large photos they could use for those three slots, and 21 smaller photos they could use for those 19 slots. Given these choices, how many different possible albums could they create?
-
(A) 3,150
(B) 4,200
(C) 5,040
(D) 20,520
(E) 84,000
In this post, we’ll discuss how to handle questions like this — without a calculator.
Combinations
Mathematically, a combination is a group of things, irrespective of order. For example, {A, B, D} and {D, A, B} and {B, A, D} are all the same combination — order doesn’t matter at all. The expression nCr (read “n choose r”) is the expression for the number of combinations of r things, r choices, you can make from a pool of n unique items. For example,
6C3 = the number of combinations of three one can choose from a pool of six unique items.
In a previous post about combinations, I give the following formula for nCr
where the exclamation point (“!”) is the factorial symbol — n! means the product of all the positive integers from n down to 1. Using this formula, we could compute the value of 6C3
So, it turns out, there are twenty ways to pick a set of three items from a pool of six unique items. That’s one way to calculate nCr, but it’s not the only way.
Pascal’s Triangle
The mathematician and philosopher Blaise Pascal (1623 – 1662) created a magical triangular array of numbers known now as Pascal’s Triangle:
How does this pattern work? Well, of course, the edges are diagonals of 1’s. Every inside number is the sum of the two numbers above it in the previous row, diagonally to the left and diagonally to the right. For example, the 2 is the sum 1+1; both 3’s are the sum 1+2; both 4’s are the sums 1+3; the 6 is the sum 3+3, etc. They often show Pascal’s Triangle to grade school students to give them practice with addition.
Despite its relatively easy origins, Pascal’s Triangle is a treasure trove of miraculous mathematical properties. Most relevant for us right now is: Pascal’s Triangle is, among other things, an array of all possible nCr’s.
nCr = the rth entry of the nth row of Pascal’s Triangle
In that definition, we have to be careful — we have to start counting at zero instead of one. The top 1 on Pascal’s Triangle is the zeroth row, zeroth entry, 0C0 = 1 (a relatively meaningless number in terms of combinations!) The next row (1, 1) is the first row, and the next row is the second row (1, 2, 1), etc. Notice that the second number in any row (as well as the penultimate number in any row) equals the row number. The first number (always 1) is actually the zeroth entry, so that second number would actually be the first entry — the first entry of the nth row always equals n. In other words
nC1 = n
That makes sense: if we have n different items, we have exactly n ways of selecting any one item. Those entries, the first entries of each row, line along a diagonal down the left side of the triangle. Because of the complete symmetry of the triangle, this always equals the numbers on the corresponding diagonals on the right side, which would be the (n-1) entries of each row. Thus:
nC1 = nC(n-1) = n
When you have to figure out nCr when n & r are both relatively small numbers, it may be easier simply to jot down the first few rows of Pascal’s Triangle. For example, with what we have showing, we can see that 6C3, the 3rd entry of the 6th row, is 20 — the same as the answer we found via the factorials formula.
Things get even more interesting when we move to the next diagonal in, shown in green here:
These numbers, the set of the second entries in each row, are the triangular numbers. Among other things, the second entry in the n row is the sum of the first n-1 positive integers. For example
3 = 2 + 1
6 = 3 + 2 + 1
10 = 4 + 3 + 2 + 1 etc.
The formula for this is:
Because we have a formula, we can calculate this for much higher numbers. For 21C2, we would have to write out everything to the twenty-first row of Pascal’s Triangle, an arduous undertaking. Rather, we could simply use the formula
Notice that the symmetry of Pascal’s Triangle also provides tremendous insight into the nature of the nCr numbers. First of all, in any row, the second entry, the triangular number in that row, must be equal to the third-to-last entry of the row, that is, the (n-2) entry of the row. Thus
Thus, via the triangular numbers, we have a formula, not only for the second entry of each row, but also for the third-to-last entry of every row. Thus, it’s very easy to figure out the first three or last three numbers in any row. More generally, symmetry guarantees that:
nCr = nC(n-r)
If you think about combinations this makes sense: if we have a pool of n unique items, then every time we choose a unique set of r items, we necessarily exclude a corresponding unique set of (n-r) items. In other words, there is necessarily a 1-to-1 correspondence between unique sets of r elements and unique sets of the other (n-r) elements —- because there’s a 1-to-1 correspondence, the number of each must always be the same. This is precisely what that equation says.
Practice
That discussion was liberally peppered with hints about how to do the above three questions. If you had trouble with them on the first pass, you may want to give them a second look before proceeding to the explanations below. Here’s an additional question from inside Magoosh:
4) http://gmat.magoosh.com/questions/847
Practice question explanations
1) Behind the story, we are really being asked to evaluate 7C3. We could use the factorial formula, but above we conveniently happen to have Pascal’s Triangle written out to the seventh row. We see that 7C3, the third entry of the seventh row, is 35. Answer = D.
2) For this one, we have to use the Fundamental Counting Principle (FCP) as well as information about combinations. For the flowers, we want 9C8, which by the symmetry of Pascal’s Triangle, has to equal 9C1, the first entry in the row, which of course equals the row number.
9C8 = 9C1 = 9
That’s the number of flower combinations. For the candles, 4C2, we read the second entry of the fourth row of Pascal’s Triangle.
4C2 = 6
Now, by the FCP, we multiply these for the total number of centerpiece arrangements: 6*9 = 54. Answer = A
3) For the large photos, we need 6C3, which we calculated in the article:
6C3 = 20
For the smaller photos, we need 21C19, which by symmetry must equal 21C2, and we have a formula for that. In fact, in the article above, we already calculated that 21C2 = 210.
Now, by the FCP, we just multiply these: total number of possible albums = 20*210 = 4200. Answer = B
Leave a Reply