This is part of our
GRE Math Essentials project & GRE Math Essentials - A most comprehensive handout!!! that are 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.
1. Each of the different orders of arrangements, obtained by taking some, or all, of a number of things, respective of the order in which the things appear in the group, is called a Permutation.
2. Each of the different groups, or collections, that can be formed by taking some, or all, of a number of things, irrespective of the order in which the things appear in the group, is called a Combination.
Permutation Vs. Combination |
Factor
| PERMUTATION
| COMBINATION
|
Meaning | Permutation can be defined as the different ways how we can arrange a set of objects in a sequence. | Combination means the different ways of choosing variables or items from a set of objects not focusing on the order of the same. |
Order | The focus is on the order of the positioning of the variables or items | Order is irrelevant in combinatorics. |
Denotes | The arrangement of variables | The selection of items in no particular order |
What does it show us? | Set of elements in a logical sequence | Sets of items without any order |
Answers | Permutation tells us how many groups can be created from a set of objects. | Combinatorics tells us how many different groups can be selected from a larger group of items. |
Example : Suppose, there are four quantities A,B,C,D. The different orders of arrangements of these four quantities by taking three at a time, are :
ABC, ACB, BAC, BCA, CAB, CBA, ... (
1)
ABD, ADB, BAD, BDA, DAB, DBA, ... (
2)
ACD, ADC, CAD, CDA, DAC, DCA, ... (
3)
BCD, BDC, CDB, CBD, DBC, DCB. ... (
4)
Thus, each of the 24 arrangements, of the four quantities A,B,C,D by taking three at a time, are each called a permutation. Hence, it is clear that the number of permutations of four things taken three at a time is 24. Hence, we see that there are only four different groups that can be formed of four quantities A,B,C,D by taking three at a time. Thus, the number of combinations of four things taken three at a time is only four.
Note:
It may be observed that the total number of permutations, as given by (1), (2), (3), (4), may be supposed to have been obtained by either :
(
1) forming all possible different groups and then rearranging the constituents of each of these groups in different orders in all possible ways; or
(
2) filling up three places by means of the four quantities A,B,C,D in all possible ways. If there are m ways of doing a thing and n ways of doing a second thing and p ways of doing a third thing, then the total number of “distinct” ways of doing all these together is \(m \times n \times p.\)
Meaning of factorial :
Factorial of a number (whole number only) is equal to the product of all the natural numbers up to that number. Factorial of n is written as \(\lfloor n\) or \(n!\) and is read as factorial n. Hence :
\(7! = 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 5040\)
\(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\)
\(n! = n (n – 1) (n – 2) \times ...... 3 \times 2 \times 1\)
NOTE :
(
1). \(0! = 1\) (
by definition)
(
2). \(nP_r = \frac{n! }{ (n – r)!}\) where \(r ≤ n\)
(
3). \(C^n_r = \frac{n! }{ [(n – r)! r!]}\) where \(r ≤ n\)
PERMUTATIONS1. Permutations of n different things taken ‘r’ at a time is denoted by \(P^n_r\) and is given by \(P^n_r\) \(= \frac{n! }{ (n – r)!}\)
2. The total number of arrangements of n things taken r at a time, in which a particular things always occurs \(= r \times P^{n-1}_{r – 1}\)
3. The total number of permutations of n different things taken r at a time in which a particular thing never occurs \(= P^{n-1}_r\)
4. The total number of permutations of n dissimilar things taken r at a time with repetitions \(= n^r\)
5.
(
a) No. of circular permutations of n things taken all at a time \(= (n – 1)!\)
(
b) No. of circular permutations of n different things taken r at a time \(= \frac{P^n_r}{r}
\)
7. The number of permutations when things are not all different : If there be n things, p of them of one kind, q of another kind, r of still another kind and so on, then the total number of permutations is given by \(\frac{n! }{ (p! q! r!...)}\)
COMBINATION1. Number of combinations of n dissimilar things taken ‘r’ at a time is denoted by \(C^n_r\) & is given by \(C^n_r= \frac{n! }{ [ (n – r)! r! ]}\)
2. Number of combinations of n different things taken r at a time in which p particular things will always occur is \(C^{n-p}_{r – p}
\)
3. No. of combinations of n dissimilar things taken ‘r’ at a time in which ‘p’ particular things will never occur is \(C^{n-p}_r \)
4. \(C^n_r = C^n_{n – r}\)
The SLOT MethodAnother perfectly valid way to complete Permutations and Combinations questions is through what's called the "Slot Method."
In fact, this is much like breaking a quadratic through the guess-and-check method, which is vastly easier than plugging it into the textbook Quadratic Equation (and if you're doing that, please stop).
While the Quadratic Equation is great for situations where the guess-and-check method is prohibitively difficult, the other side of that coin is that it's unnecessarily time-consuming for simple questions.
Going back to P&C: for GRE-level P&C questions, you are unlikely to see anything that really requires pulling out these equations, and they might actually just confuse the issue because they make it difficult to understand what's really going on.
This comes down to asking yourself three Core Questions:
--How Many Spaces?
--How Many Choices?
--Does Order Matter?
Let's take an example: We have seven paintings from which to choose, and three places to hang them on the wall.
Question 1: In how many distinct orders can we hang three paintings?
DO NOT ask whether it's P or C yet; just ask the questions, and that will become apparent:
--How many spaces? 3, naturally.
_ _ _
--How many choices? 7 from which we choose.
>here, just multiply counting down from the 7...
7*6*5
--Does order matter?
>we are looking for DISTINCT ORDERS, so YES -- if YES, it is a Permutation.
That means that we do not need to proceed further. Our answer is 7P3 = 210.
Question 2:
How many distinct groups of three paintings can be hung?
DO NOT ask whether it's P or C yet; just ask the questions, and that will become apparent:
--How many spaces? 3, naturally.
_ _ _
--How many choices? 7 from which we choose.
>here, just multiply counting down from the 7...
7*6*5
--Does order matter?
>we are looking for GROUPS OF THREE, wherein the order of the group doesn't matter, so NO. If NO, it is a Combination.
>At this point, we need to divide by the factorial of the group size (3), because we are treating painting abc=acb=bac=bca=cab=cba, or essentially counting one for every six.
--You can say that dividing by the factorial of group size "randomizes" the numbers within the bag.
7*6*5 / 3! = 7*5 = 35
So our answer is 7C3 = 35.
NOTE on Randomization:
Rather than paintings, let's imagine seven different-colored marbles placed into a box that holds three. Obviously, those would be in some particular order. That means that abc is distinct from acb is distinct from bac and so on. That means each of these is counted as different.
Imagine that we pick up the box and shake it. Now we know which three were chosen, but we have no indication of the order that they currently are in. Dividing by the factorial of group size (3! in this case) is essentially like picking up the box and shaking it.
How this discussion relates to those ever-present equations:
For 7P3, you'll see that n = 7 and r = 3. Therefore, if you plug in 7!/(7-3)! = 7*6*5 you'll find yourself where we were at the beginning, just without the extra work.
For 7C3, you'll see that n = 7 and r = 3. Therefore, if you plug in 7!/(3!(7-3)!) = (7*6*5)/3! = 35. Again, less work.
Some people like the equations and that's totally fine. Pick what works for you. It's good to know multiple ways to do things.
The MISSISSIPI RuleA useful mnemonic device for the n!/(p!q!r!...) case is called "The Mississippi Rule."
It is as follows: if you ask yourself how many ways you can rearrange the letters in the word "Mississippi," not assuming the letters to make any sense, you would get:
total!/(repeats!)
11!/(4!4!2!) = number of ways to organize the letters in "Mississippi"
In this case, the total number of letters is 11. There are four Is, four Ss, and two Ps.
Not recommended to calculate this fully (the answer is 34650); it is primarily useful as a way to remember the principle.
Counting any group that has repeated terms can be done using the Mississippi Rule, so any time you see something in the form:
AABBB = 5!/(2!3!)
or CCCCDDDD = 8!/(4!4!)
etc. you can apply this calculation.
Thanks to
PGTLrowanhand for the two methods above
source of reference :
Difference Between Permutation and Combination by
Surbhi SAttachment:
GRE P&C (2).jpg [ 73.15 KiB | Viewed 15802 times ]
Attachment:
GRE P&C.jpg [ 47.07 KiB | Viewed 29961 times ]
Attachment:
screenshot.192.jpg [ 19.17 KiB | Viewed 50423 times ]
Attachment:
GRE Permutation VS Combination.jpg [ 37.05 KiB | Viewed 16404 times ]
Attachment:
GRe permutation verus combination.jpg [ 32.95 KiB | Viewed 13487 times ]
Attachment:
GRE prep club permutation combination.jpg [ 34.76 KiB | Viewed 28726 times ]