Skip to main content

Chapter 23 Exercises

Exercises Exercises

1.

Recall the following two definitions.

  • The order of a permutation \(p\) is the smallest positive integer \(k\) such that \(p^k\) is the identity.

  • A permutation \(p\) is an involution if \(p^2\) is the identity permutation.

Note that the identity permutation is an involution. In fact, the identity is the only involution of order 1. The remaining involutions have order 2. For any \(k \geq 1\text{,}\) let \(g_{n,k}\) be the the number of \(n\)-permutations \(p\) that are \(k\)-volutions, meaning that that \(p^k\) is the identity. Let \(h_{n,k}\) be the number of \(n\)-permutations \(p\) of order \(k\text{.}\) For \(k >1\text{,}\) we always have \(g_{n,k} > h_{n,k}\text{,}\) because the identity is a \(k\)-volution of order \(1 < k\text{.}\)

Let \(G_k(x) = \sum_{n=0}^{\infty} g_{n,k} \frac{x^n}{n!}\) and \(H_k(x) = \sum_{n=0}^{\infty} h_{n,k} \frac{x^n}{n!}\) be the exponential generating functions for these sequences. We have

\begin{equation*} G_1(x) = H_1(x) = \exp(x) \end{equation*}

since the identity permutation is the only \(1\)-volution. Example 4.36 on page 202 shows that

\begin{equation*} G_2(x) = \exp \left( x + \frac{x^2}{2} \right) \end{equation*}

and therefore

\begin{equation*} H_2(x) = \exp \left( x + \frac{x^2}{2} \right) - \exp\left( x \right) \end{equation*}

  1. Find \(G_3(x)\) and \(H_3(x)\text{.}\)

  2. Find \(G_4(x)\) and \(H_4(x)\text{.}\)

  3. Let \(k \geq 1\) and suppose that \(p^k\) is the identity. Explain why the order of \(p\) must divide \(k\text{.}\) Use this fact to find a formula for \(G_k(x)\text{.}\)

  4. Find a formula for \(H_{6}(x)\) in terms of \(G_{k}(x)\) where \(1 \leq k \leq 6\text{.}\)

  5. Find a formula for \(H_{30}(x)\) in terms of \(G_{k}(x)\) where \(1 \leq k \leq 30\text{.}\)