Combinatorics - GMAT Math Study Guide

Definitions

• Combinatorics - The branch of mathematics that deals with collections of objects that satisfy specified criteria (e.g., counting arrangements, permutations, and combinations).
  For example, combinatorics would answer the question "how many different ways can you arrange a 10-song playlist if you have 45 songs to choose from?"
• Combinations - The branch of combinatorics where changing the order of the objects does not create a new scenario.
  For example, the question "how many teams of 9 baseball players can a manager assemble from a roster of 18 players?" is a combinations question since changing the order in which the player is chosen does not create a new arrangement (see combinations for much more on this topic).
• Permutations - The branch of combinatorics where changing the order of the objects creates a new scenario.
  For example, the question "how many different ways can a baseball pitcher who throws 6 unique pitches (e.g., curveball, fastball, changeup, etc.) throw the next 3 pitches?" is a permutations question because changing the throwing order creates a new arrangement (e.g., throwing fastball, sinker, changeup is different than throwing sinker, changeup, fastball) (see permutations for much more on this topic).

Factorials

Solving permutations and combinations problems using a formula requires the use of factorials. x factorial, denoted x!, is the product of all positive integers less than or equal to x.

5 factorial, denoted 5!

Another Example:

Another Example:

Simplifying Factorials

Complicated expressions using multiple factorials often contain overlapping terms and can be simplified considerably.

Permutations

Permutations involve problems in which the arrangement of the items in question does matter. Some examples of common problems are arranging books on a bookshelf, creating a seating chart or making a schedule. In all of these situations, moving things around creates a different arrangement, chart, or schedule. (If changing the order of the items in question creates a uniquely different arrangement, you are dealing with a permutation).

There are two general ways to solve these problems. The first method involves drawing the problem. The second involves the use of a formula. For simpler problems it is often possible to draw the arrangement. However, as the problems become more difficult, drawing the problem can become more prone to errors and using the formula may be best.

n = the number of objects to choose from
k = the number of objects selected

Consider the following example:

If there are six students and six desks in an art class, how many different seating arrangements are there?

Solving with a picture:
__ __ __ __ __ __ __
There are six spots to be filled. The first student who enters the class has six choices (or possible seats).
The second student has five choices (or possible seats).
The third student has four choices (or possible seats).
The fourth student has three choices (or possible seats).
The fifth student has two choices (or possible seats).
The sixth student has no choice (only one seat left).
Thus, there are 6*5*4*3*2*1 = 6! = 720 seating arrangements.

Solving with the equation:
n = 6 = number of possible seats to choose from
k = 6 = number of seats that will be chosen

Combinations

Unlike permutations, combinations do not consider order. The number of possible euchre hands or the number of teams that can be created in a gym class are just a few examples. In both cases, the order does not matter. A team consisting of Jimmy, Dan, and Bob is the same as a team consisting of Dan, Jimmy, and Bob.

Unlike permutations, combinations cannot be easily solved by diagramming the problem. Instead, use the equation below to solve combination problems.

n = the number of objects to choose from
k = the number of objects selected

This equation can be read as having n objects and choosing to arrange k of them (i.e., you are selecting k objects from a pile of n objects). The k! on the bottom represents how switching two objects around no longer creates a new arrangement.

Consider the following example:

If there are 2 intern positions open at a firm with 5 applicants, how many different combinations of applicants could be hired?

Plugging the information from the problem into the equation:

The equation tells us that if we have five applicants and are choosing two individuals, there are 10 different ways to do this.

Types of GMAT Problems

1. Identical Objects

   Sometimes identical objects are involved in the arrangements. If the identical objects are switched, the arrangement remains unchanged. Thus, these two different arrangements are actually the same. The formula to determine the number of arrangements possible when identical objects are involved is as follows:
   
   Where n stands for the total number of objects, and the k_i stands for the number of the i^th type of object.

   How many different unique combinations of letters can be created by rearranging the letters in mathematics?

   A)	2!
   B)	10!
   C)	8!/3
   D)	11!/6
   E)	11!/8

   Correct Answer: E

   1. Count the number of times each letter is repeated and the total number of letters.
      Letters Occurring Once: s,e,h,i,c -- five letters
      Letters Occurring Twice: m,a,t -- three letters
      Total Number of Letters, n = 5*1 + 3*2 = 11
   2. It is important to notice that this question asks about the number of "unique combinations." As a result, if the repeated letters in mathematics are switched, the word remains unchanged. Consequently, we must take account for the duplicated letters since rearranging these will not produce a different combination of letters.
   3. Use the formula for repeated items.
      
      The three instances of 2! in the denominator take into account the fact that three letters each occur twice.
   4. Because 11! is a very large number and there is no factorial in the denominator to cancel it out, there is no more simplification to be done.
2. Circular Arrangements

   For arrangements that do not have an end or beginning (circular), it is key to realize that shifting all the objects to the right or left will not change anything. The objects will still have the same neighbors and relative positions. Thus a new equation is required to determine the number of possible arrangements for scenarios with a circular setup. For n objects there will be (n-1)! circular arrangements. However, it is also possible to determine the number of arrangements by using one object as the beginning and working outwards.

   If a class of 10 students has five men, how many ways can the men and women be arranged in a circle so that no two men sit next to each other?

   A)	5!4!
   B)	5!5!
   C)	4!4!
   D)	10!
   E)	10!/5!

   Correct Answer: A

   1. If no two men sit next to each other, then the seats must be filled man-woman-man-woman etc.
   2. Place a man in the first seat. The next seat must be a woman, the following a man, and so on.
   3. Although there are five men to choose from in the first seat, it does not matter which man is chosen (this is a really important insight and is due to the fact that we are dealing with a circle). The next seat (i.e., the seat to the side of the first man) has 5 choices as there are 5 women left to be seated next to the male in the anchor seat. The next seat will have 4 choices since there are 4 men left. The next seat will have 4 choices since there are 4 women left. The next seat will have 3 choices since there are 3 men left. The next seat will have 3 choices since there are 3 women left.
      
   4. Since this question trips up many students, here is an alternative way of explaining it. Note that whether a man or woman is the first to be seated is irrelevant. Note as well that whether we place individuals down going clockwise or counterclockwise is also irrelevant:
      First Seat: Place one individual of Gender A down
      Second Seat: Place one individual of Gender B down (5 people of Gender B to choose from)
      Third Seat: Place one individual of Gender A down (4 people of Gender A to choose from)
      Fourth Seat: Place one individual of Gender B down (4 people of Gender B to choose from)
      Fifth Seat: Place one individual of Gender A down (3 people of Gender A to choose from)
      Sixth Seat: Place one individual of Gender B down (3 people of Gender B to choose from)
      Seventh Seat: Place one individual of Gender A down (2 people of Gender A to choose from)
      Eighth Seat: Place one individual of Gender B down (2 people of Gender B to choose from)
      Ninth Seat: Place one individual of Gender A down (1 person of Gender A to choose from)
      Tenth Seat: Place one individual of Gender B down (1 person of Gender B to choose from)
   5. Thus, the total number of possible arrangements is 5*4*4*3*3*2*2*1*1 = 4!*5! = (n-1)!(n!) = 24*120 = 2880