What happens when Permutations have repeat elements?
Posted on
25
Feb 2021

What happens when Permutations have repeat elements?

By: Rich Zwelling, Apex GMAT Instructor
Date: 25th February, 2021

Permutations With Repeat Elements

As promised in the last post, today we’ll discuss what happens when we have a PERMUTATIONS situation with repeat elements. What does this mean exactly? Well, let’s return to the basic example in our intro post on GMAT combinatorics:

If we have five distinct paintings, and we want to know how many arrangements can be created from those five, we simply use the factorial to find the answer (i.e. 5! = 5*4*3*2*1 = 120). Let’s say those paintings were labeled A, B, C, D, and E. 

Now, each re-arrangement of those five is a different PERMUTATION, because the order is different:

ABCDE
EBADC
CADBE


etc

Remember, there are 120 permutations because if we use the blank (or slot) method, we would have five choices for the first blank, and once that painting is in place, there would be four left for the second blank, etc…

_5_  _4_  _3_  _2_  _1_ 

…and we would multiply these results to get 5! or 120.

However, what if, say we suddenly changed the situation such that some of the paintings were identical? Let’s replace painting C with another B and E with another D:

ABBDD

Suddenly, the number of permutations decreases, because some paintings are no longer distinct. And believe it or not, there’s a formulaic way to handle the exact number of permutations. All you have to do is take the original factorial, and divide it by the factorials of each repeat. In this case, we have 5! for our original five elements, and we now must divide by 2! for the two B’s and another 2! for the two D’s:

  5!
——
2! 2!     

= 5*4*3*2*1
   ————-
  (2*1)(2*1)

= 5*2*3
= 30 permutations

As another example, try to figure out how many permutations you can make out of the letters in the word BOOKKEEPER? Give it a shot before reading the next paragraph.

In the case of BOOKKEEPER, there are 10 letters total, so we start with a base of 10! 

We then have two O’s, two K’s and three E’s for repeats, so our math will look like this:

   10!
———
2! 2! 3! 

Definitely don’t calculate this, though, as GMAT math stays simple and likes to come clean. Remember, we’ll have to divide out the repeats. You are extremely unlikely to have to do this calculation for a GMAT problem, however, since it relies heavily on busy-work mechanics. The correct answer choice would thus look like the term above. 

Let’s now take a look at an Official Guide question in which this principle has practical use. I’ll leave it to you to discover how. As usual, give the problem a shot before reading on:

A couple decides to have 4 children. If they succeed in having 4 children and each child is equally likely to be a boy or a girl, what is the probability that they will have exactly 2 girls and 2 boys?

(A) 3/8
(B) 1/4
(C) 3/16
(D) 1/8
(E) 1/16

Quick Probability Review

Remember from our post of GMAT Probability that, no matter how complicated the problem, probability always boils down to the basic concept of:

    Desired Outcomes
———————————–
Total Possible Outcomes

In this case, each child has two equally likely outcomes: boy and girl. And since there are four children, we can use are blank method to realize that we’ll be multiplying two 4 times:

_2_  _2_  _2_  _2_   =  16 total possible outcomes (denominator)

This may give you the premature notion that C or E must be correct, simply because you see a 16 in the denominator, but remember, fractions can reduce! We could have 4 in the numerator, giving us a fraction of 4/16, which would reduce to 1/4. And every denominator in the answer choices contains a factor of 16, so we can’t eliminate any answers based on this. 

Now, for the Desired Outcomes component, we must figure out how many outcomes consist of exactly two boys and two girls. The trick here is to recognize that it could be in any order. You could have the two girls followed by the two boys, vice versa, or have them interspersed. Now, you could brute-force this and simply try writing out every possibility. However, you must be accurate, and there’s a chance you’ll forget some examples. 

What if we instead write out an example as GGBB for two girls and two boys? Does this look familiar? Well, this should recall PERMUATIONS, as we are looking for every possible ordering in which the couple could have two girls and two boys. And yes, we have two G’s and two B’s as repeats. Here’s the perfect opportunity to put our principle into play:

We have four children, so we use 4! for our numerator, then we divide by 2! twice for each repeat:

  4!
——
2! 2! 

This math is much simpler, as the numerator is 24, while the denominator is 4. (Remember, memorize those factorials up to 6!)

This yields 6 desired outcomes of two boys and two girls. 

With 6 desired outcomes of 16 total possible outcomes, our final probability fraction is 6/16, which reduces to 3/8. The correct answer is A.

Next time, we’ll look into combinatorics problems that involve restrictions, which can present interesting conceptual challenges. 

Permutations and Combinations Intro
A Continuation of Permutation Math
An Intro To Combination Math
Permutations With Repeat Elements
Permutations With Restrictions
Combinations with Restrictions
Independent vs Dependent Probability
GMAT Probability Math – The Undesired Approach
GMAT Probability Meets Combinatorics: One Problem, Two Approaches

Read more
Featured Video Play Icon
Posted on
03
Sep 2020

Data Sufficiency Problem

 

I’m here with a number theory data sufficiency problem. Like many of the other problems, we’re going to look at this problem over here, structurally, as well as mathematically. Taking a look at the stem the first thing we are struck by is the idea that we need to figure out this evenness and oddness.

What Do We Need?

When we ask ourselves what do we need: a few things should draw our attention: First, that one of these elements is squared. So if B is squared then no matter what it is its square will have the same identity: even squared is even, odd squared is odd. But also because we’re adding these two things together, for something to be odd one of them has to be odd, the other has to be even. But it could go either way so there’s a lot of moving pieces. The easiest thing to do is to say: “I need to know if each of them is even or odd.” But, of course, we know that the GMAT is not going to give us this information.

Start With Statement 1

Let’s take a look then at statement one and statement two. And because statement one is very straightforward we should begin there. So here we’re told very quickly succinctly: one is even one is odd. We can run a scenario and plug in some numbers, a two and a three for example, or deal with it at the identity level Either way, that gives us a straight answer that is sufficient. If that’s not visible to you I would suggest that you review your number properties. In general, this is enough and we say: “Okay, well, one’s sufficient.”

Statement Number 2

Then we get into number two and we have this “B plus C” is odd and immediately we might end up dismissing this and this would be a mistake. The reason we end up dismissing it is because one was so straightforward in addressing what we needed that two feels like because B and C aren’t extricated from each other that it’s almost too complex. So the GMAT may have lulled us into a sense of security with statement number one, which I think is one of the really neat structural features of this problem. If statement one were more complex we would actually spend more time looking at statement two.

Diving into statement two a little more deeply we can see that because B plus C is odd rather than even one must be even the other must be odd. And because it doesn’t matter which, something that we ascertained when we were looking at the question stem which is why that proactive thinking is really important, we can say well as long as one is each then that’s going to be sufficient as well. And so here the answer is D.

Further Information

I want to put up a third piece of information. And this is a really useful thing to do when you’re self-prepping is to look at data sufficiency and then postulate what other piece of information might have some subtlety, might the GMAT give us to induce us to an incorrect answer by modulating the complexity not in the question stem but in the introduced information. So here we have C equals B over 2. What this means is B must be even. Take a minute to think about that. We can’t know anything about C but B must be even because they’re integers and because you can slice B into two B is the even one. It’s tempting to move that 2 over and say 2C equals B and say: “Wait, C is even.”

But if you think about that a little more deeply it doesn’t add up because what we’re doing is multiplying C. An odd or an even number times 2 is going to result in an even. So this is a really great problem form because the same pattern of even/odd identities with different embedded equations and different ways of hiding whether B or C or M, N, or X and Y, or P and Q are odd or even is a very common trope especially as you get to the more challenging levels of the GMAT where you have these abstract DS questions, abstract inequalities that are really the bread and butter of 700 plus.

Examine This Problem Form Deeply

So as a more general problem form this is one to examine deeply and play around with in a whole bunch of different ways. You can introduce exponents, absolute value, inequalities as I mentioned, quadratic identities are a big one where, for example, you have a difference of two squares and then you’ve got one piece or the other, the X plus Y or X minus Y and they give you information on that. And so as you’re doing this, one of the most important pivot questions to look at is: “How do I convert this piece of information into the information they’re asking me about in the question stem?” or vice versa: “How do I relate this information in the question stem to this piece of information?” because almost certainly they’re going to be related and it’s in that relationship that you determine whether or not it’s sufficient.

And typically as the subtleties increase that relationship is what defines the entire problem. I realize that’s a little meta but these questions are a little meta. So I hope this helps! Wishing you guys a great day and like and subscribe below and we’ll see you real soon!

If you found this data sufficiency problem video helpful, try your hand at this percentage problem or this probability problem.

 

 

Read more