Combinations & Permutations
Consider the following: How many different pairings of 2 letters can you make out of the 3 letters, a, b, and c, without considering their arrangement? It becomes readily apparant that the answer is 3, namely, ab, ac, and bc. Remember we said no consideration is to be given to their arrangement so ab and ba are the same pairing, ac and ca are the same, as are bc and cb. These pairings, without consideration of their arrangement, we refer to as combinations.
If you were asked to determine the number of different arrangements of 2 letters out of the same 3 letters, a, b, and c, you would come up with 6, namely ab, ba, ac, ca, bc, and cb. These pairings, accounting for their arrangements, we refer to as permutations.
To be specific, each of the "arrangements" which can be made by taking some, or all, of a number of things from a group of things, is called a permutation. Each of the "groups", or selections, which can be made by taking some or all of a number of things from a group is called a "combination." Thus, the permutations which can be made by taking the letters a, b, c, d two at a time are twelve in number; namely, ab, ac, ad, bc, bd, cd, ba, ca, da, cb, db, dc; each of these presenting a different "arrangement" of two letters. The combinations which can be made by taking the letters a, b, c, d two at a time are six in number; namely, ab, ac, ad, bc, bd, cd; each of these representing simply a different selection of two letters ignoring their arrangement.
From this it is clear that in forming combinations we are only concerned with the number of things each selection contains; whereas in forming permutations we have also to consider the "order" of the things which make up the arrangement; for instance, if from four letters a, b, c, d we make a selection of three, such as abc, this single "combination" is capable of being "arranged" in the following ways: abc, acb, bca, bac, cab, cba, and so gives rise to six different "permutations."
Permutations
We designate the permutations of n things taken n at a time as nPn and the permutations of n things taken r at a time as nPr where P stands for permutations, n stands for the number of things involved, and r is less than n. To find the number of permutations of n dissimilar things taken n at a time, the formula is nPn = n! which is n factorial which means n(n-1)(n-2)(n-3).......3x2x1. Example: How many ways can you arrange the letters A & B. Clearly 2 which is 2 x 1 = 2. How many ways can you arrange the letters A, B & C in sets of three? Clearly 3P3 = 3 x 2 x 1 = 6. How many ways can you arrange A, B, C & D in sets of four? Clearly 4P4 = 4 x 3 x 2 x 1 = 24.
To find the number of permutations of n dissimilar things taken r at a time, the formula is nPr = n(n-1)(n-2)(n-3)..........(n-r+1). Example: How many 3-place numbers can be formed from the digits 1, 2, 3, 4, 5, and 6, with no repeating digit? Then we have 6P3 = 6x5x(6-3+1) = 6x5x4 = 120. How many 3-letter arrangements can be made from the entire 26 letter alphabet with no repeating letters? We now have 26P3 = 26x25x(26-3+1) = 26x25x24 = 15,600. Lastly, four persons enter a car in which there are six seats. In how many ways can they seat themselves? 6P4 = 6 x 5 x 4 x (6-4+1) = 6x5x4x3 = 360.
Another permutation scenario is one where you wish to find the permutations of n things, taken all at a time, when p things are of one kind, q things of another kind, r things of a third kind, and the rest are all different. Without getting into the derivation, nPn(p,q,r,s) = n!/(pxqxr). For example, how many different permutations are possible from the letters of the word committee taken all together? There are 9 letters of which 2 are m, 2 are t, 2 are e, and 1 c, 1 o, and 1 i. Therefore, the number of possible permutations of these 9 letters is 9P9(2,2,2,1,1,1) = 9!/(2x2x2x1x1x1) = 362,880/8 = 45,360.
Combinations
We designate the combinations of n things taken n at a time as nCn and the combinations of n things taken r at a time by nCr. To find the number of combinations of n dissimilar things taken r at a time, the formula is nCr = n!/[r!(n-r)!] which can be stated as n factorial divided by the product of r factorial times (n-r) factorial. Example: In how many ways can a committee of three people be selected from a group of 12 people? We have 12C3 = (12!)/[3!(9!) = 220. How many different ways can you combine A, B, C, and D in sets of three? Clearly, 4C3 = (4x3x2x1)/(3x2x1)(1) = 4. How many handshakes will take place between six people in a room when they each shakes hands with all the other people in the room one time? Here, 6C2 = (6x5x4x3x2x1)/(2x1)(4x3x2x1) =15.
Another way of viewing combinations is as follows. Consider the number of combinations of 5 letters taken 3 at a time. This produces 5C3 = 5x4x3x2x1/(2x1)(3x2x1) = 10. Now assume you permute (arrange) the r = 3 letters in each of the 10 combinations in all possible ways. Each group would produce r! permutations. Letting x = 5C3 for the moment, we would therefore have a total of x(r!) different permutations. This total, however, represents all the possible permutations (arrangements) of n things taken r at a time, which we earlier defined as nPr. Therefore, x(r!) = nPr or x = nPr/r!. But, x = nCr which results in nCr = nPr/r!. Using the committee of 3 out of 12 people example from above, 12C3 = (12x11x10)/3x2x1 = 220.
Consider the following: How many different ways can you enter a 4 door car? It is clear that there are 4 different ways of entering the car. Another way of expressing this is 4C1 = 4!/1! = 4. If we ignore the presence of the front seats for the purpose of this example, how many different ways can you exit the car assuming that you do not exit through the door you entered? Clearly you have 3 choices. This too can be expressed as 3C1 = 3!/1! = 3. Carrying this one step further, how many different ways can you enter the car by one door and exit through another? Entering through door #1 leaves you with 3 other doors to exit through. The same result exists if you enter through either of the other 3 doors. Therefore, the total number of ways of entering and exiting under the specified conditions is 4x3 = 12 or 4C1 x 3C1 = 4 x 3 = 12. Another example of this type of situation is how many ways can a committee of 4 girls and 3 boys be selected from a class of 10 girls and 8 boys? This results in 10C4 x 8C3 = [(10x9x8x7)/(4x3x2x1)] x [(8x7x6)/(3x2x1)] = 210 x 56 = 11,760.
<--------------------------------------------------------------------------------------------------------------->
Each of the "arrangements" which can be made by taking some, or all, of a number of things, is called a permutation. Each of the groups, or selections, which can be made by taking some or all of a number of things is called a "combination." Thus, the permutations which can be made by taking the letters a, b, c, d two at a time are twelve in number; namely, ab, ac, ad, bc, bd, cd, ba, ca, da, cb, db, dc; each of these presenting a different "arrangement" of two letters.
The combinations which can be made by taking the letters a, b, c, d two at a time are six in number; namely, ab, ac, ad, bc, bd, cd; each of these representing simply a different selection of two letters.
From this it is clear that in forming combinations we are only concerned with the number of things each selection contains; whereas in forming permutations we have also to consider the "order" of the things which make up the arrangement; for instance, if from four letters a, b, c, d we make a selection of three, such as abc,
this single combination is capable of being arranged in the following ways: abc, acb, bca, bac, cab, cba, and so gives rise to six different "permutations."
To find the number of permutations of n dissimilar things taken r at a time, the formula is P(n/r) = n! which is n factorial which means n(n-1)(n-2)(n-3).......(n-r+1). Example: How many ways can you arrange the letters A & B. Clearly 2 which is 2 x 1 = 2. How many ways can you arrange the letters A, B & C in sets of three? Clearly P(3/3) = 3 x 2 x 1 = 6. How many ways can you arrange A, B, C & D in sets of four? Clearly P(4/4) = 4 x 3 x 2 x 1 = 24. Four persons enter a car in which there are six seats. In how many ways can they seat themselves? P(6/4) = 6 x 5 x 4 x (6-4+1=3) = 360.
To find the number of combinations of n dissimilar things taken r at a time, the formula is C(n/r) = n!/r!(n-r)! which can be stated as n factorial divided by the product of r factorial times (n-r) factorial. How many different ways can you combine A, B, C, and D in sets of three? Clearly, C(4/3) = (4x3x2x1)/(3x2x1)(1) = 4. How many
handshakes will take place between six people in a room when they each shakes hands with all the other people in the room one time? C(6/2) = (6x5x4x3x2x1)/(2x1)(4x3x2x1) =15.
