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 ...

Start Free Trial

No credit card required