An Introduction to the Analysis of Algorithms, Second Edition

Chapter Seven. Permutations

Combinatorial algorithms often deal only with the relative order of a sequence of N elements; thus we can view them as operating on the numbers 1 through N in some order. Such an ordering is called a permutation, a familiar combinatorial object with a wealth of interesting properties. We have already encountered permutations: in Chapter 1, where we discussed the analysis of two important comparison-based sorting algorithms using random permutations as an input model; and in Chapter 5, where they played a fundamental role when we introduced the symbolic method for labelled objects. In this chapter, we survey combinatorial properties of permutations and use probability, cumulative, and bivariate generating functions ...