Question: Books on a Shelf

Comment on Books on a Shelf

Dear Brent: I am trying to understand the difference in the fundamental counting principle(FCP) and permutations. IN the first video in this module, you introduced us to the FCP with the example of building a car. Where each "slot"/stage represented the three options. The result was 18 unique options. Now, are permutations a method for arranging tasks within each "slot" where the outcome are not all unique, such as in this example (eg. out of the 144 ways to arrange these books, many will not be unique).

Can you please give me tip for how to conceptionally separate the FCP and the N! method? What confuses me is that if you just use the FCP results are unique but you can also use it in combination with the N!, so what is a good way to marry the topics? Would appreciate tips on how to differentiate these two concepts.


Many thanks!


gmat-admin's picture

Permutations, the "N! method" and the FCP are all members of the same family. They all require us to break a task into stages.

For example, if we want to arrange 6 objects in a row, we can use the FCP and see that the first position can have 6 different objects, the second position can have 5 different objects, the third position can have 4 different objects, etc. And when we multiply the stages, we get (6)(5)(4)(3)(2)(1).

Or we can just use the N! formula, which says N objects can be arranged in a row in N! ways.

We essentially used the FCP to derive the N! formula, so either method is fine.

Permutations fall into the same category, except I'm not a big fan of teaching permutations since there are very few true permutation questions on the GMAT, and since we can use the FCP to solve permutation questions anyway.

More on this here: https://www.gmatprepnow.com/articles/combinations-and-non-combinations-%...

How could we arrange the subjects in 6 ways here? I am unable to understand.
gmat-admin's picture

We can arrange n objects in n! ways. So, we can arrange the 3 subjects (math, art and history) in 3! ways (= 6 ways)

By the way, here are the 6 ways:

1) math, art, history
2) math, history, art
3) history, art, math
4) history, math, art
5) art, history, math
6) art, math, history

Cheers,
Brent

How does this question different from MISSISSIPPI Rule?
How does this question compare with the question: how many different ways can we arrange the 7 letters MMMAAHH?
gmat-admin's picture

Good question jpshow.

The difference here is that we're told the 3 math books are all DIFFERENT. Likewise, the 2 art books are different and the 2 history books are different.

The MISSISSIPPI Rule involves arranging a group of items in which some of the items are IDENTICAL (like the letters S, S, S and S)

Cheers,
Brent

What about this solution:

Stage 1 : Selecting book for position number 1. 7 Ways
Stage 2 : If it is a Math, then the 2nd book can be selected in 2 ways
Stage 3 : last Math book in 1 way
Stage 4 : Selecting Art book. 2 ways
Stage 5 : Selecting the 2nd Art book. 1 way
Stage 6 : Selecting History book. 2 ways
Stage 7 : Selecting the 2nd History book. 1 way.

FCP: 7*2*4*2= 112

What is wrong with this approach?
gmat-admin's picture

That's a good start, but what do you do if the first book isn't a Math book?

Thanks for the prompt reply.

I thought of that! But in the below question, The solution provided (I believe from you) followed the same approach.

https://www.beatthegmat.com/seating-arrangement-t222030.html

What am I missing here?
gmat-admin's picture

While the above video question is similar to the question at https://www.beatthegmat.com/seating-arrangement-t222030.html, the big difference is that, in the linked question, there is symmetry among the 3 groups of people. Each group consists of ONE PAIR of people from the same country.

The video question doesn't have that kind of symmetry, and this non-symmetry leads to the statement "If it (the 1st book) is a Math, then the 2nd book can be selected in 2 ways"

So, in your solution, you only (kind of) consider the arrangement MATH|ART|HISTORY.
However, there are 5 more arrangements we must consider, such as ART|HISTORY|MATH, MATH|HISTORY|ART, and more.

So, one option would be to consider ALL SIX cases and determine the number of arrangements in each case.

For example, CASE A: MATH|ART|HISTORY
Book 1 (math book) can be selected in 3 ways
Book 2 (math book) can be selected in 2 ways
Book 3 (math book) can be selected in 1 way
Book 4 (art book) can be selected in 2 ways
Book 5 (art book) can be selected in 1 way
Book 6 (history book) can be selected in 2 ways
Book 7 (history book) can be selected in 1 way
Total arrangements = (3)(2)(1)(2)(1)(2)(1) = 24 ways

CASE B: ART|HISTORY|MATH
Book 1 (art book) can be selected in 2 ways
Book 2 (art book) can be selected in 1 way
Book 3 (history book) can be selected in 2 ways
Book 4 (history book) can be selected in 1 way
Book 5 (math book) can be selected in 3 ways
Book 6 (math book) can be selected in 2 ways
Book 7 (math book) can be selected in 1 way
Total arrangements = (2)(1)(2)(1)(3)(2)(1) = 24 ways

CASE C: MATH|HISTORY|ART
Book 1 (math book) can be selected in 3 ways
Book 2 (math book) can be selected in 2 ways
Book 3 (math book) can be selected in 1 way
Book 4 (history book) can be selected in 2 ways
Book 5 (history book) can be selected in 1 way
Book 6 (art book) can be selected in 2 ways
Book 7 (art book) can be selected in 1 way
Total arrangements = (2)(1)(2)(1)(3)(2)(1) = 24 ways

As you might guess, each case has 24 possible arrangements.
So, the TOTAL = (24)(6) = 144

Hi Brent,

I was following your explanation to the question given in this link : https://gmatclub.com/forum/team-a-and-team-b-are-competing-against-each-other-in-a-game-241461.html#p1877882

I am trying to understand how this question differs from the "books" question in the video. Why are we not doing 3!(Arrange men) * 3!(Arrange Women) * 3!(Arrange Men-Women pairs) just as we arranged Subjects(in addition to arranging individual Maths,Arts & Historys books) in the Video Question.

Thanks & Regards,
Abhirup
gmat-admin's picture

Question link: https://gmatclub.com/forum/team-a-and-team-b-are-competing-against-each-...

You've suggested a valid approach, except for the last part (3!).

Here's how that approach would look:

STAGE 1: Arrange the 3 males from left to right
We can complete this stage in 3! ways (= 6 ways)

STAGE 2: Arrange the 3 females from left to right
We can complete this stage in 3! ways (= 6 ways)

STAGE 3: Combine the two groups so that we have male-female-male-female-male-female.
We can complete this stage in 1 way

So, the total number of arrangements = (6)(6)(1) = 36

NOTE: Some students will not see that STAGE 1 can be completed in only 1 way.
Let me try to convince them of this.

Let's say that, in STAGE 1, we arranged the 3 males as follows:
1st = Joe, 2nd = Al, and 3rd = Ed

And let's say that, in STAGE 2, we arranged the 3 females as follows:
1st = Sue, 2nd = Ann, and 3rd = Bea

In STAGE 3, we'll combine them to go in the order: male-female-male-female-male-female.
Since the 1st person is male, the 1st person will be Joe (since he's first among the males)
The 2nd person is female. So, the 2nd person will be Sue (since she's first among the females)
3rd person = Al
4th person = Ann
5th person = Ed
6th person = Bea

So, once we've completed STAGES 1 and 2, there's only one way to arrange the 6 people.

Does that help?

Cheers,
Brent

Thanks Brent for your response. Building further on your explanation, will I be correct to assume that since a Joe-Sue-Al-Ann-Ed-Bea arrangement is same as a Al-Sue-Joe-Ann-Ed-Bea arrangement(any such arrangement as long as MFMFMF constraint is maintained order doesn't matter) there isn't any STAGE 3.
Lets consider a variation of the same problem. A 6 digit key needs to be created using the numbers 2,4,6,3,5,9, having the order Odd-Even-Odd-Even-Odd-Even. As per my understanding our solution will change slightly since order matters in this case.
STAGE 1 : 3! for arranging Odd nos.
STAGE 2 : 3! for arranging Even nos.
STAGE 3: 3! for arranging Odd-Even pairs since I know 2-3-4-5-6-9 is different from 4-3-2-5-6-9

Really appreciate your assistance in clarifying this doubt.

Thanks & Regard,
Abhirup
gmat-admin's picture

I think we're trying too hard to make an unnecessarily complicated strategy work for us.

Consider your approach to the odd-even-odd question:
STAGE 1 : 3! for arranging Odd nos.
STAGE 2 : 3! for arranging Even nos.
STAGE 3: 3! for arranging Odd-Even pairs since I know 2-3-4-5-6-9 is different from 4-3-2-5-6-9

First off, if you've already arranged the ODD values (e.g., 5-3-9) and you've already arranged the EVEN values (e.g., 6-2-4), then there's only 1 way to arrange them as odd-even-odd-even-odd-even: 5-6-3-2-9-4
Notice that the odds are in the order 5-3-9 and the evens are in the order 6-2-4
So, STAGE 3 can be completed in 1 way

Now, rather arrange the evens and odds separately and THEN try to combine both sets of values, let's just select a number for each space.

STAGE 1: Select the 1st number: Since the 1st number is odd, we have 3 options.
STAGE 2: Select the 2nd number: Since the 2nd number is even, we have 3 options.
STAGE 3: Select the 3rd (odd) number: Since we've already used 1 odd in stage 1, we have 2 odd options remaining.
STAGE 4: Select the 4th (even) number: Since we've already used 1 even in stage 2, we have 2 even options remaining.
STAGE 5: Select the 5th number: 1 way
STAGE 6: Select the 6th number: 1 way
Answer = (3)(3)(2)(2)(1)(1) = 36

Cheers,
Brent

Thanks Brent! I got confused but now I feel a sense of clarity thanks to your explanation.

Hi Brent, what if the question asked us to arrange the subjects in any order ? What would be the number of ways for this ? And second case, what would be the number of ways if each subject had the same book and there were 2 books for each subject ?
gmat-admin's picture

1) What if the question asked us to arrange the subjects in any order?
The question does allow for subjects to be arranged in any order (e.g., History-Math-Art or Math-History-Art or Art-History-Math or Math-Art-History, etc

2) What would be the number of ways if each subject had the same book and there were 2 books for each subject?
In this case, the answer would be 3! (6), since all we'd need to do is arrange the 3 subjects, which can be done in 3! ways. Once we've arranged the 3 subjects, we just place two (identical) books in each section.

Does that help?

Cheers
Brent

Thank you for the quick response. Yes this clears my confusion. What I meant for the first part of my question is what if the books could be arranged in any way. For example, math book with history book and history book with art book and so on. I think I understood now.
This should be 7! ways since there are 7 books in total.
gmat-admin's picture

Thanks for the clarification.
You're absolutely right. If we remove the restriction that says books of the same topic must be arranged together, then we can arrange all seven books in 7! ways.

Hi Brent,
What if all books would be grouped randomly ? I wonder the answer woulde be like this ?
7! x 6! x 5!
gmat-admin's picture

If the 7 books and be arranged in any order, then we can do sew in 7! ways (since we are arranging 7 unique objects)
That is, we have 7 options for the first book in the arrangement.
We have 6 options for the second book in the arrangement.
We have 5 options for the third book in the arrangement.
And so on

You’re Learning to Count!

Sure, when you word it like that, it doesn’t sound very impressive, but you know how tricky these counting questions can be.  

Change Playback Speed

You have the option of watching the videos at various speeds (25% faster, 50% faster, etc). To change the playback speed, click the settings icon on the right side of the video status bar.

Have a question about this video?

Post your question in the Comment section below, and a GMAT expert will answer it as fast as humanly possible.

Free “Question of the Day” emails!