Solving an implicit equation to find the exponential generating function of a specific sequence

Question

Suppose we have a set $A$ with $n$ elements. First we partition $A$ in at least two blocks. Then, we partition each block in the previous partition that is not of size 1 in at least two blocks. We continue like this until we have a partition of $A$ with only blocks of size 1. We call this procedure a total partition of $A$.

For example, the following is a total partition of the set $A=[7]$.

$$ \{\{1,2\},\{3,4,5\},\{6,7\}\}\implies\{\{1\},\{2\},\{3\},\{4,5\},\{6\},\{7\}\} \\ \implies\{\{1\},\{2\},\{3\},\{4\},\{5\},\{6\},\{7\}\} $$

Let $a_n$ be the number of total partitions of a set with $n$ elements. I have to find the exponential generating function of the sequence $\{a_n\}$, which I will denote by $G(x)$. To do this, I first had to find an implicit equation which is satisfied by $G(x)$. I found the following equation:

$$ G(x)=x+e^{G(x)}-G(x)-1 $$

which details I will skip since it is a quite long explanation. Futhermore I am certain that this equation is right, since my professor told me it was right, and because later I have to prove that the inverse function to $G(x)$ is $2x-e^x+1$, which is equivalent to the implicit equation I already found.

From that implicit equation, I'm guessing I have to solve for $G(x)$ and then write somethings that would appear on the equation as power series in order to obtain the explicit expresion for $G(x)$. I'm thinking this since all of the examples I have seen where generating functions are used to solve recurrence relations use this method, or a similar one. However, I don't know how to solve for $G(x)$ here, any help you could give me is appreciated.

Answer 1

Hint: You do not need to solve for $G(x)$, and I believe doing so is impossible. You just need to find $G^{-1}(x)$. A defining property of $G^{-1}(x)$ is $$G^{-1}(G(x))=x$$Therefore, a strategy for this problem is to rearrange the equation $G(x)=x+e^{G(x)}-G(x)-1$ so that it looks like $$ \text{expression which is function of $G(x)$}=x $$ and then conclude that that function on the LHS is $G^{-1}$.

An example of this: Let $t_n$ be the number of complete, ordered, unlabeled ternary trees on $n$ nodes, and let $T(x)=\sum_{n\ge 1} t_n x^n$. Standard generating function trickery implies $$ T(x)=x+xT(x)^3 $$ This can be written in the form $$ \frac{T(x)}{1+T(x)^3}=x, $$ which implies that the inverse function of $T(x)$ is $$T^{-1}(y)=\frac{y}{1+y^3}.$$

Answer 2

I'm looking to complement Mike Earnest's answer. Indeed, let's write $y=G(x)$ and rearrange our equation to $$x=2y+e^y+1.$$ We know how to write the right-hand side as a power series in $y$. Indeed, we have $$x=2+3y+\sum_{n=2}^{\infty} \frac{y^n}{n!}.$$ We want to find a solution $y$ of the form $$y=\sum_{m=0}^{\infty}a_m x^m.$$ So, we plug this into our equation and expand out the right-hand side (I'm not going to do all of the hard work for you)... \begin{align*} x&=2 + 3\left(\sum_{m=0}^\infty a_m x^m\right) + \sum_{n=2}^\infty\frac1{n!}\left(\sum_{m=0}^{\infty}a_m x^m\right)^n\\ &=\left(2+3a_0+\frac{1}{2!}a_0^2+\frac{1}{3!}a_0^3+\ldots\right)+\text{higher order terms} \end{align*} Comparing coefficients shows that $$0=2+3a_0+\frac{1}{2!}a_0^2+\frac{1}{3!}a_0^3+\ldots=1+2a_0+e^{a_0}.$$ Already, we see issues with the uniqueness of solution. Sure, this equation has a unique solution $a_0$ in the real numbers, but it has infinitely many solutions in the complex numbers. These different solutions can be seen as coming from the different branches of the Lambert $W$-function.