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**

Hi Mike,

Thank you for all the posts and videos! Really helping me a lot!

I have a query about the 3rd question? For 21C19, isn’t it possible that 19! gets cancelled from both the numerator as well the denominator which leaves us with 21*20? Wouldn’t that follow the combination rules as well?

Thanks!

Hi Rohan,

Yes, if you were to complete the combination 21C19, the 19! would cancel from the numerator and denominator. However, you are forgetting that the denominator has second component: (n-r)!

The combination formula is nCr=n!/r!(n-r)!

So in this question we would have 21!/(19!*2!). The 19! cancels out of the numerator and denominator, but the 2! remains and we are left with: (21*20)/(2*1), which equals 210. This is why we say that 21C19=12C2–they are essentially the same formula!

Hi,

I have a magoosh premium account for GMAT. Combinatorics has always been a weak area for me. Though i have improved my skills , i still need some more guidance in order to master this area.

Can you please provide me some good resources where i can get some extra practice ?

Regards,

Raunaq

Hi Raunaq,

Thanks for your question. Since you’re a Premium Magoosh student, I went ahead and forwarded your question on to our team of remote tutors. Someone from that team will reach out to you via email.

Best of luck!

Dani

Hi McGarry Sir,

I have a magoosh premium account, and combinatorics is my weakest spot. Please guide me on good resources for good content practise questions on combinatorics for extra practise.

Hi Debashree,

Just a heads up that I sent your question over to our team of tutors. A tutor will be responding to you directly via email with some ideas about resources for combinatorics.

Have a great day!

Jessica

Hello guys,

Shouldn’t the 3rd question be a permutation one as the order will matter on the album eventually as all the photographs large or small would be all different.

Hey alan…i am happy to help in regards to your inquiry. Suppose you choose 3 large photos form the pool of 6 photos. Let us first name these photos as A, B, C. Now let us paste these photos in the album. i pasted it as A B C. Now suppose if i paste this as B A C or C B A, my outcome is not going to change and it remains the same. The photo album will still contain these three photos within itself and whatever shuffling happens among them, selection doesn’t change. Hence here order doesn’t matter and we need to go ahead with combination.

On the contrary, if the problem was framed like, there are 3 different border designs on the album for large photos and each border design is for a particular type of photo, then things would be different and its no longer a combination problem since if we change the order, different photos will have different order changing the selection anyway!

Hope this clears your doubt.

So I agree with you up to this:

“Now suppose if i paste this as B A C or C B A, my outcome is not going to change and it remains the same.”

I would consider albums with the same photos but different arrangements to be different albums. If they had used language like “groups” or “selections”, fine. But nothing in the language of the question gives us permission to disregard order.

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?

Dear Mike,

In this why can’t we just add their probabilities, i mean like two of four different candles i.e 4c2 + 8 of 9 different flowers i.e 9c8 or 9c1 which sums to 15.?

Mike-

Thank you for the very informative posts. I have a question about question #2 at the beginning of this blog. Please tell me what am I missing here. Here it goes:

Should we use permutation instead of combination for the centerpiece arrangement question? She has to use 2 candles from 4 choices. I don’t know much about the centerpiece arrangements but, hear me out please! There are 10 slots to be filled with 2 different types of candles and 8 different types of flowers. And there are 10 empty slots – A, B, C, D, E, F, G, H, I, and J, okay? Wouldn’t the order in which flowers and candles fill these slots matter? Wouldn’t a centerpiece in which a rose scented candle is put in slot A be different from a centerpiece different from a centerpiece in which the same rose scented candle is put in slot B? So, that way there will be 4 X 3 X 9! arrangements. What am I missing here?

Thanks!

Dear Vijay,

You know, for that question, I didn’t want people considering how the centerpiece might be arranged. FWIW, centerpieces are usually somewhat circular, and definitely are not candles & flowers all in a row. Given two candles and eight flowers, how many different centerpieces could one design with different spacial configurations? That question is truly mind-boggling, and has no straightforward answer.

I changed the text of the question, to make more clear what is actually being asked. Does it make sense now?

Mike 🙂

Yes, sir! Thank you!

Vijay,

you are more than welcome. Best of luck to you.

Mike 🙂