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