Finding closed form of exponential generating function involving identity permutation

221 Views Asked by At

Fix a prime number $p > 1$ and for a positive integer $n$, let $a_n$ be the number of permutations $π ∈ S_n$ such that $π^p = id$, where $id$ is the identity permutation. Find a closed form for the exponential generating function $B(x) = \sum_{n\ge0}a_n\frac{x^n}{n!}$.

I believe the closed form of

$$\sum_{n\ge0}n!\frac{x^n}{n!}$$

is $\frac{1}{1-x}$ but the inclusion of $a_n$ confuses me.

1

There are 1 best solutions below

1
On

The fact that $p$ is prime greatly simplifies things. We get the combinatorial class

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}(\textsc{CYC}_{=1}(\mathcal{Z})+ \textsc{CYC}_{=p}(\mathcal{Z})).$$

This immediately produces the EGF

$$G(z) = \exp\left(z+\frac{z^p}{p}\right).$$

Extracting the coefficient we find

$$n! [z^n] G(z) = n! [z^n] \exp(z^p/p) \exp(z) = n! \sum_{q=0}^{\lfloor n/p \rfloor} \frac{1}{p^q \times q! } \frac{1}{(n-qp)!}.$$

This yields e.g. for $p=7:$

$$1, 1, 1, 1, 1, 1, 721, 5761, 25921, 86401, 237601, \\ 570241, 1235521, 892045441, \ldots$$

which points to OEIS A053497, where these data are confirmed.