# 7.   Permutations

This chapter surveys combinatorial properties of permutations (orderings of the numbers 1 through N) and shows how they relate in a natural way to fundamental and widely-used sorting algorithms.

## 7.3

How many permutations of $2n$ elements have exactly two cycles, each of length $n$? How many have $n$ cycles, each of length $2$?

## 7.4

Which permutations of $n$ elements have the maximum number of different representations with cycles?

## 7.8

Write a program that will compute the canonical cycle representation corresponding to a given permutation.

## 7.9

Write a program that will compute the permutation corresponding to a given canonical cycle representation.

## 7.10

Give an efficient algorithm for computing the inversion table corresponding to a given permutation, and another algorithm for computing the permutation corresponding to a given inversion table.

## 7.24

Show that the number of involutions of size $N$ satisfies the recurrence $$b_{N+1} = b_N + Nb_{N-1}\quad{\rm for}\ N>0{\rm \ with\ } b_0=b_1=1.$$

## 7.27

By differentiating the relation $(1-z)D(z)=e^z$ and setting coefficients equal, obtain a recurrence satisfied by the number of derangements of $N$ elements.

## 7.29

An arrangement of $N$ elements is a sequence formed from a subset of the elements. Prove that the EGF for arrangements is $e^z/(1-z)$. Express the coefficients as a simple sum and interpret that sum combinatorially.

## 7.45

Find the CGF for the total number of inversions in all involutions of length $N$. Use this to find the average number of inversions in an involution.

## 7.61

Use asymptotics from generating functions (see Section 5.5) or a direct argument to show that the probability for a random permutation to have $j$ cycles of length $k$ is asymptotic to the Poisson distribution $e^{-\lambda}\lambda^j/j!$ with $\lambda=1/k$.
{"ft_lang_label":"__label__en","ft_lang_prob":0.7536258,"math_prob":0.99648,"size":2147,"snap":"2019-51-2020-05","text_gpt3_token_len":548,"char_repetition_ratio":0.14372376,"word_repetition_ratio":0.03154574,"special_character_ratio":0.23381463,"punctuation_ratio":0.097256854,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999583,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-12-14T01:54:29Z\",\"WARC-Record-ID\":\"<urn:uuid:4fdf9558-d14e-473e-8ad9-4ee0f93c354f>\",\"Content-Length\":\"9162\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:c67562d8-b401-4820-bd08-5034482107c0>\",\"WARC-Concurrent-To\":\"<urn:uuid:a398d043-7457-4c31-a12f-a48fa1738b22>\",\"WARC-IP-Address\":\"128.112.136.51\",\"WARC-Target-URI\":\"https://aofa.cs.princeton.edu/70permutations/\",\"WARC-Payload-Digest\":\"sha1:4L6ACK2IZP6TOGMRSUQIZESRCMHMJJKV\",\"WARC-Block-Digest\":\"sha1:ZY7LDKGGDZYYZ7OI7ARWNOPOFEHRRWHI\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-51/CC-MAIN-2019-51_segments_1575540579703.26_warc_CC-MAIN-20191214014220-20191214042220-00531.warc.gz\"}"}