ABSTRACT

We define the canonical cycle notation of permutations, and present Dominique Foata's bijection connecting it to permutations in one-line notation. We count permutations of a given cycle structure, and permutations with a given number of cycles. An explicit formula is presented for the Stirling numbers of the first kind. Exponential generating functions in one and two variables are used to enumerate permutations with a restricted cycle structure. We revisit the notion of odd and even permutations, analyze the array of signless Stirling numbers https://www.w3.org/1998/Math/MathML"> c ( n , k ) https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429274107/76d8f3df-fdac-4af3-ad29-e5f6ca3c54a5/content/math00_2.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/> of the first kind, and use Darroch's theorem to find the value of https://www.w3.org/1998/Math/MathML"> k https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429274107/76d8f3df-fdac-4af3-ad29-e5f6ca3c54a5/content/math00_3.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/> that maximizes https://www.w3.org/1998/Math/MathML"> c ( n , k ) https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429274107/76d8f3df-fdac-4af3-ad29-e5f6ca3c54a5/content/math00_4.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/> for a fixed value of https://www.w3.org/1998/Math/MathML"> n https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429274107/76d8f3df-fdac-4af3-ad29-e5f6ca3c54a5/content/math00_5.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/> .