How to use Lagrange inversion to count derangements?

Question

Let $\mathcal{D_n}$ be the class of derangements, i.e. the class of permutations without fixpoints, on $[n]$ and set $\mathcal{D} = \cup_{n \ge 1} \mathcal{D}_n$. We know that the EGF of $\mathcal{D}$ is given by

$$D(z) = \frac{1}{1 - T(z)},$$

where $T(z)$ is the EGF of the class of Cayley trees. Use Lagrange inversion to find a sum formula for $[z^n]D(z)$.

I do not see how to apply the Lagrange inversion here, as this would require the form $y(z) = zD(y(z))$, which I can not see for the above term. Could you please give me a hint?

Answer 1

You mentioned the Lagrange inversion theorem. I assume that the statement of the problem you are referring to is something like this:

Lagrange inversion theorem: Let $\phi$ is an analytic function at $z=0$, such that $\phi(0)\neq 0$. Let $y(z)$ be an analytic function defined by the equation $y(z)=z\cdot \phi(y(z))$. Then $$[z^n]y(z)=\frac1n[w^{n-1}]\phi(w)^n$$

I do not know how to directly apply this formula to your case. As you noted, we do not have a functional equation for $D(z)$ in the required form. We do have the well-known functional equation for $T(z)$, namely $T(z)=ze^{T(z)}$, but we want the coefficients for $D(z)=\frac1{1-T(z)}$, not $T(z)$ itself.

Fortunately, there is an extension of LIF which fulfills this exact need, called the Lagrange–Bürmann formula.

Lagrange–Bürmann formula: With the same assumptions as the last theorem, for any analytic function $H$, we have
$$ [z^n]H(y(z))=\frac1n[w^{n-1}]\Big(H'(w)\phi(w)^n\Big) $$

Applying this with $y(z)\gets T(z)$, $\phi(w)\gets e^w$, $H(w)\gets \frac1{1-w}$, we get $$ [z^n]D(z) =[z^n]\frac1{1-T(z)} =[z^n]H(T(z)) =\frac1n[w^{n-1}] \left(H'(w)\phi(w)^n\right) =\frac1n[w^{n-1}] \left(\frac{1}{(1-w)^2}e^{nw}\right) $$ You should now be able to extract the coefficient of $w^{n-1}$ in the last expression on your own.