Counting Permutations

Abstract

Suppose we have an orange, an apple and a pear. How many different ways can we arrange these three? The answer is six – OAP, APO, PAO, OPA, AOP, POA. These arrangements are called permutations. Now, how large a collection of these arrangements can we have so that any two arrangements have one fruit in the same position? With our three fruit, the answer is two. One example would be OAP and OPA. The answer isn’t quite so easy if we start with a larger set of objects. You would probably be surprised at the number of years it took for mathematicians to prove an answer that would apply to any number of objects. It turns out that the best approach is to have one object in the same position in all the arrangements. What happens if any two arrangements must have two objects in the same positions? What about more than two? How large a collection of permutations will meet these constraints? Recently, Ellis, Friedgut and Pilpel arrived at a partial answer to this question. In the research for my Master's thesis at the University of Regina, I used a different approach in an attempt to solve this problem. I will present these two results and discuss the relative strengths of each.