What's the meaning of setting a power symmetric polynomial to a given value

Question

I was reading an involutive introduction to symmetric functions of Mark Wildon. In particular, I was trying to understand how to derive the derangements of $S_n$ with symmetric functions. In the book the result appears as Corollary $1.12$, which is the following:

Corollary 1.12

(i) Let $d_n$ be the number of derangements in $\text{Sym}_n$. Then $$\frac{d_n}{n!} = 1 - \frac{1}{1!} + \frac{1}{2!} - \cdots + \frac{(-1)^n}{n!}.$$

(ii) Let $O_n$ be the number of derangements in $\text{Sym}_n$ that have an odd number of cycles, and let $E_n$ be the number of derangements in $\text{Sym}_n$ that have an even number of cycles. Then $O_n - E_n = n-1$.

(iii) Let $o_n$ be the number of derangements in $\text{Sym}_n$ that are odd permutations, and let $e_n$ be the number of derangements in $\text{Sym}_n$ that are even permutations. Then $o_n - e_n = (-1)^n(n-1)$.

Proof. Let $\mathcal{D}_n$ be the set of derangements in $\text{Sym}_n$. For (i) and (ii) specialize the version of the Cycle Index Formula in (8) by setting $p_1 = 0$ and $p_k = z$ for $z \geq 2$, where $z$ is an indeterminate. We get

$$\exp \sum_{k=2}^\infty \frac{z t^k}{k} = \sum_{n=0}^\infty \frac{t^n}{n!} \sum_{\sigma \in \mathcal{D}_n} z^{\text{cyc}(\sigma)}$$

where $\text{cyc}(\sigma)$ is the number of cycles in $\sigma$. Setting $z=1$ we get

$$\frac{\exp(-t)}{1-t} = \exp \left ( -t - \log(1-t) \right ) = \sum_{n=0}^\infty \frac{d_n}{n!} t^n.$$

Taking the coefficient of $t^n$ on the left hand side gives (i).

...

In particular I don't understand the meaning of setting $p_0 = 1$ and $p_k = z$ for $k \geq 2$. This should enclose the information of derangements but I don't see how, since I'm thinking to those as polynomials, I would have expected to evaluate $p_k$ in some value, such as $(1,\cdots,1)$ to get a "number" from the start, but this came after. Any help or explanation would be appreciated.

Answer 1

In the cycle index formula the $p_i$ are a countable set of indeterminates, not the power symmetric polynomials. They can be specialized to the power symmetric polynomials and this is interesting to do for various reasons but they don't have to be. So there's no issue with specializing them to some other values, or other indeterminates, etc.

Said another way the cycle index formula is an identity of generating functions with coefficients in the ring of polynomials in countably many variables $p_i$.

Answer 2

We start with identity (1.9) from the paper \begin{align*} \exp\sum_{k=1}^{\infty}\frac{p_k}{k}t^k=\sum_{n=0}^{\infty}\frac{1}{n!} \sum_{\sigma\in\mathrm{Sym}_n}p_1^{\mathrm{cyc}_1(\sigma)}\cdots p_n^{\mathrm{cyc}_n(\sigma)}t^n\tag{1.9} \end{align*}

• Setting $p_1=0$ (and not $p_0=1$) in the right-hand side of (1.9) means we do not count permutations with fixed points, leaving precisely the permutations in $\mathrm{Sym}_n$ which are derangements. The identity (1.9) reduces to \begin{align*} \exp\sum_{k=2}^{\infty}\frac{p_k}{k}t^k=\sum_{n=0}^{\infty}\frac{1}{n!} \sum_{\color{blue}{\sigma\in D_n}}p_2^{\mathrm{cyc}_2(\sigma)}\cdots p_n^{\mathrm{cyc}_n(\sigma)}t^n\tag{2.1} \end{align*} where the left-hand side starts with $k=2$ and at the right-hand side we sum over all permutations which are derangements $\color{blue}{\sigma\in D_n}$.

• Since we just want to count the number of derangements we do simplifications in two steps. At first we simplify the expression (2.1) further by substituting each parameter $p_2,\ldots,p_n$ with $z$ which gives \begin{align*} \exp\sum_{k=2}^{\infty}\frac{z}{k}t^k=\sum_{n=0}^{\infty}\frac{1}{n!} \sum_{\sigma\in D_n}z^{\mathrm{cyc}(\sigma)}t^n \end{align*} This way we do not any longer differentiate between different cycle lengths at the right-hand side. Furthermore it's now easy to get the wanted representation by letting $z=1$. Otherwise we would have to cope with substituting tuples $(1,1,\ldots,1)$ of different length at the left-hand side and at the right-hand side of (2.1) which is slightly more cumbersome.

• Setting now $z=1$ we have $\sum_{\sigma\in D_n}z^{\mathrm{cyc}(\sigma)}=d_n$. We obtain \begin{align*} \color{blue}{\exp\sum_{k=2}^{\infty}\frac{t^k}{k}=\sum_{n=0}^{\infty}\frac{d_n}{n!}t^n}\tag{2.2} \end{align*} and some more simplifications of the left-hand side of (2.2) can follow.