Teacher resources and professional development across the curriculum
Teacher professional development and classroom resources across the curriculum
• Counting permutations is different than simply counting combinations because order must be taken into account.
So far we have learned how to consider both ordered and unordered subsets. How might our results change if we require that the arrangements be circular? To put this into context, let's phrase all our previous problems in terms of dinner parties. In this scenario n! is the number of ways of putting n people along one side of a banquet table. C(n,k) is the number of ways of choosing k people out of n to sit together at a table. What if we have circular tables, however, and we want to count the number of ways that a given number of people can be arranged around one of these?
Suppose we are expecting ten people for dinner; how many ways can we seat them around a circular table? First, let's think about how many ways we can line them up. As we indicated above, there will be 10! ways to line up ten guests: ten for the first position, nine for the second, eight for the third, and so on.
How does this change if they are seated around a circular table? Concepts such as this are called circular permutations, and they are not exactly like linear permutations.
Notice that every circular arrangement corresponds to ten different linear arrangements.
Using our reasoning from before, we can see that the number of circular arrangements is equal to the number of linear arrangements, 10!, divided by ten to compensate for the fact that each circular permutation corresponds to ten different linear ones. This gives as the number of ways to arrange ten guests around a table. We can generalize this to say that n elements can be arranged in (n-1)! ways around a circle.
It may seem to you that problems such as these are just more examples of mathematicians' hypothetical word problems, but this problem of circular arrangement pops up yearly in England. Every year in June, a procession and service take place at Windsor Castle for the Order of the Garter—England's oldest order of chivalry (founded by Edward III in 1348.) Following the installation of new members in the Throne Room, the Queen of England and Duke of Edinburgh host a luncheon for members and officers of the Order in Waterloo Chamber. Tradition holds that seating charts for the luncheon are rotated so that no two guests will have sat next to one another in the last ten years.
With forty-five people to consider, this problem could pose quite a headache if we attacked it with the brute force method. If order matters, there are 44! possible arrangements, which is about 1054. Checking just one of these arrangements per second would take 1046 years, which is about thirty-six orders of magnitude longer than the universe has been in existence. Recall, however, that we need ten consecutive years in which nobody has sat next to the same person twice. This means that we need to check all of the subsets of ten arrangements out of a possible 44!, which is C(44!,10). This number is much larger—yet another combinatorial explosion.
Of course, using the organizing principles of combinatorics, there is a better way. We could represent the forty-five members and their connections to each other as a diagram of forty-five points, all of which are connected to one another.
Such a diagram is called a graph, with each point being a node, and each connection an edge. A graph in which every node is connected to every other node is called a complete graph. The standard notation for a complete graph with n nodes is Kn. So, a complete, forty-five-node graph would be referred to as K45.
The actual graph of K45 is quite large, so it may be helpful to examine a smaller version to see the idea.
If we had just five people, A, B, C, D, and E, our complete K5 graph would look like that in the diagram. We can come up with circular table arrangements of these five people by looking at paths that visit all the nodes exactly once and return to the start. Such a configuration is known as a Hamilton cycle. Remember that a connection on the graph represents two people sitting next to each other. In our current problem related to seating the Order of the Garter luncheon guests we are concerned with Hamilton cycles that share no common edges. Such cycles are said to be mutually disjoint. Two of these cycles for a five-person arrangement are shown in the diagram.
Notice that with these two cycles, every edge is accounted for. So, although we may be able to construct other cycles, they will always include at least one of the edges that we've already used. This means that there are two, and only two, mutually disjoint Hamilton cycles for an arrangement of five elements. Consequently, we could have only two annual luncheons, at most, before two of the five people sat next to each other again.
We can see why there can be no more than two mutually disjoint arrangements in this situation by thinking about it from the perspective of one of the people seated at the table, let's say it's the queen. The queen will always sit next to two people, one on her right and one on her left. In the K5 case, there are only four other “non-queen” people to sit by, so the queen will have sat next to everyone after two years.
We can use similar lines of reasoning with arrangements of more people. For example, to find mutually disjoint, circular arrangements of seven or nine people, we can look at possibilities within the K7 and K9 graphs, respectively.
Notice that K7 has three mutually disjoint Hamilton cycles within it and K9 has four. Applying the queen's perspective and reasoning as we did before, we can deduce that there cannot be more than three years of non-duplicate seating for seven people and not more than four years for nine people. Extending this reasoning to the original problem, that of forty-five people, we see that the queen has forty-four possible luncheon neighbors. Taken two at a time, one on her right and one on her left, it would take her twenty-two years to sit by each one.
This means that in our banquet group of forty-five members of the Order of the Garter, there can be at most twenty-two arrangements in which no two people sit next to each other more than once. In fact, twenty-two is always attainable— more than enough for ten years' worth of banquets. In general, the graph K2n+1 will always have n disjoint Hamilton cycles incorporated within it.
Finding possible orderings of dinner guests efficiently turns out to require some quite interesting math involving graphs and circuits. These concepts are applicable in other areas as well, and they can be used to show why certain relationship structures, such as mutual friendship or mutual unfamiliarity, must exist in randomly selected groups of people. Next, we will look at Ramsey Theory and how it can be used to find organization in a number of situations.
Next: 2.6 Ramsey Theory