Counting Arrangements of Objects in a Set
Date: 01/17/2006 at 23:27:22 From: Mia Subject: My question is about patterns, and different ways of arrangi A set containing two elements can be arranged in two different ways (for elements a and b, it can be ab or ba). I need to find out in how many ways can sets containing three, four, five or six elements be arranged. I figured out that the set 123 can be arranged in six ways: 123, 321, 231, 213, 312 and 132. But it takes too long to do by switching places of the elements. Is there an easier way to do it? Thanks, Mia.
Date: 01/18/2006 at 10:06:34 From: Doctor Greenie Subject: Re: My question is about patterns, and different ways of arrangi Hello, Mia -- Yes, there is an easy way to find these numbers of ways of arranging the elements for different sizes of sets. One way to understand the formula for the number of ways to arrange the elements of a set is to consider "filling the blanks" one element at a time. In your simple example with a set consisting of the two elements a and b, we want to find the number of ways of filling two blanks: __ __ We have two choices for the element to put in the first blank--a or b. Once we have chosen the element for the first blank, we have only one choice left for the second blank. So for each of the two choices for filling the first blank we have one choice for filling the second. The "for each" indicates multiplication; so the number of ways of arranging the two elements of this set is 2*1 = 2 Note that we tend to think of filling the blanks left to right, but that is not necessary. We can choose to fill the second blank first if we want; we will still have two choices for the first blank we fill and one choice for the second, giving us a total of 2*1=2 ways to arrange the elements. So what happens if, for example, we have a set consisting of 5 elements? We have 5 choices for the element to place in the first blank we fill. For each of those 5 choices, we have 4 choices for the element to place in the second blank we fill, giving us 5*4=20 ways to fill the first two blanks. Then for each of those 5*4=20 choices for the first two blanks, we have 3 choices for the element to place in the third blank we fill, giving us 5*4*3=60 ways to fill the first three blanks. And so on, until all the blanks are filled. The total number of ways of filling the 5 blanks is 5*4*3*2*1 = 120 Similarly, the number of ways of arranging the elements of a set with 10 elements would be 10*9*8*7*6*5*4*3*2*1 = 3628800 The preceding is a common explanation for the formula for the number of ways to arrange the elements of a set. Following is another approach to finding the formula. This approach is more difficult to understand; however, it demonstrates a very powerful technique for finding patterns: we find the number of arrangements for a particular number of elements, and then we add one more element and see how that changes the number of arrangements. So let's go back to our simple case where we have found that there are two ways to arrange the elements in a 2-element set: ab ba Now we add a third element to the set, c. What arrangements can we make with the three elements? The original two elements can still be in either of the two orders they were in when the set contained only two elements--either a is before b, or b is before a. For each of those two orderings of a and b, what choices do we have for where to place element c? We can place the new element before the two original elements, or we can place it between them, or we can place it after them. So for the case where a is before b, we get the arrangements cab acb abc And for the case where b is before a, we get the arrangements cba bca bac So with a 2-element set we had a total of 2 possible arrangements of the elements; and when we added a third element, we got 3 different arrangements from each of the 2 different arrangements of the original two elements. So adding the third element to the set multiplied the number of arrangements by 3. So the number of arrangements for a 3-element set is 3*2 = 6. Consider then adding a 4th element d to the set. For each of the 6 arrangements we have for 3 elements, there are 4 different places we can put the 4th element. For example, from the arrangement "abc" of the first 3 elements, we can get the following 4 arrangements: dabc adbc abdc abcd So adding the 4th element to the set gives us a total of 4*6=24 arrangements of the elements. Then you can see the pattern: adding a 5th element would give us a total of 5*24 = 120 elements; adding a 6th would give us 120*6 = 720 elements; and so on. I hope all this helps. Please write back if you have any further questions about any of this. - Doctor Greenie, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.