This is part of our
GRE Math Essentials - A most comprehensive handout!!! is the best complement to our
GRE Math Book. It provides a cutting-edge, in-depth overview of all the math concepts from basic to mid-upper levels. The book still remains our hallmark: from basic to the most advanced GRE math concepts tested during the exam. Moreover, the following chapters will give you many tips, tricks, and shortcuts to make your quant preparation more robust and solid.
Combinatorics: An Intuitive Approach
Combinatorics is a fascinating branch of mathematics dealing with counting, arrangements, and selections. Understanding the underlying logic behind permutations and combinations can make it both intuitive and enjoyable. Let’s explore this in an accessible way, focusing on how to effectively solve problems using clear, step-by-step logic.
1. Factorial and Basic ArrangementsThe backbone of combinatorics is the concept of factorial (!). Factorial represents the total number of ways to arrange a set of items where the order matters. For example:
• The factorial of 5, denoted as 5!, is the number of ways to arrange 5 distinct books on a shelf: \(5!=5×4×3×2×1=120\)
This means there are 120 ways to arrange 5 books in a linear order. Factorials give us a clear way to calculate how many different possible outcomes exist when every item is involved in the arrangement.
2. Linear vs Circular Arrangements• Linear Arrangements \((n!)\): In linear arrangements, every item has a unique position, and the arrangement is straightforward, as seen in the bookshelf example. The order of placing books matters, and every permutation counts as a different arrangement.
• Circular Arrangements \({(n-1)!}\): The case is different when arranging items in a circle (e.g., arranging people around a circular table or books on a circular shelf). Here, rotating the circle does not change the relative positions. For n distinct items, the number of circular arrangements is given by (n - 1)! For instance, arranging 5 books on a circular shelf: \((5 - 1)! = 4! = 24\)
Here, shifting the whole circle by one position doesn't create a new arrangement.
3. The Mississippi Problem ConceptWhen we have repeated elements (like the repeating letters in "MISSISSIPPI"), we need to account for the fact that swapping identical elements doesn't create new arrangements. The general formula for the number of distinct arrangements of a word with repeated letters is:
\(\frac{n!}{(p1!*p2!*p3!*...*pk!)}\)
where:
• n is the total number of letters (or items),
• p1, p2, ..., pk are the counts of each repeating letter (or item).
a. SPINThe word "SPIN" contains 4 distinct letters: S, P, I, N. Since there are no repeating letters, the number of distinct arrangements is simply the factorial of the total number of letters:
\(4! = 4×3×2×1 = 24\)
Thus, there are 24 distinct ways to arrange the letters in "SPIN."
b. DEMANDNext, let's consider "DEMAND." The total number of letters is 6, but in this case, the letter "D" appears twice. To account for the repetition of "D," we use the formula:\( \frac{6!}{2!} = \frac{6×5×4×3×2×1}{(2x1)} = \frac{720}{2} = 360\)
So, there are 360 distinct ways to arrange the letters in "DEMAND."
c. DEMANDEDFor "DEMANDED," we have 8 total letters, and two letters repeat: "D" appears three times, and "E" appears twice. We account for both repetitions using the formula:
\(\frac{8!}{(3!*2!)} = \frac{8×7×6×5×4×3×2×1}{(3×2×1)*(2×1)} = 8x7x3x5x4 = 3360\)
Thus, there are 3,360 distinct ways to arrange the letters in "DEMANDED."
4. Combinations: Choosing without Concern for OrderThe idea of combinations involves selecting items where the order of selection does not matter. The general formula for combinations is:
\(nCr = \frac{n!}{{r!(n – r)!}}\)
where n is the total number of items and r is the number of items to be chosen.
For example, 7C3 refers to choosing 3 dresses for a 3-day trip from 7 available options. Using the formula:
\(7C3 = \frac{7!}{{3!(7−3)!}} =\frac{7×6×5x4!}{(3!*4!)} = 35\)
Thus, there are 35 ways to select 3 dresses.
5. Combining Selection and ArrangementSometimes, you may need to choose a subset of items and then arrange them. In such cases, combinations are used first to select the subset, followed by permutations to arrange the selected items. This situation is common when both selection and arrangement matter.
For instance, after selecting 3 dresses from 7 options, you may also want to arrange them by day (which dress to wear on which day). This requires multiplying by the number of ways to arrange 3
items:
\(7C3 × 3! = 35 × 6 = 210\)
\(7C3\) (this is the same logic as \(nPr → nPr = \frac{n!}{(n – r)!}\)).
This means there are 210 ways to choose and arrange 3 dresses for a 3-day trip.
Tip: You can just think of nPr as nCr * r! (choose, then arrange) to keep it simple.
6. Combinatorics in Competitions: Matches Between TeamsAnother practical application of combinatorics is calculating the number of matches in a tournament. Suppose 20 teams are playing, and each team plays against every other team exactly once. The number of matches can be calculated using combinations:
\(20C2 = \frac{20!}{[2!(20−2)!] }= \frac{20×19*18!}{(2!*18!) }= 190\)
Here, we choose 2 teams from a pool of 20 to play a match.
Attachment:
combinatorics.jpg [ 52.96 KiB | Viewed 69729 times ]