Composition of formal power series of exp and log I'm considering the formal power series $$\exp(X)=\sum_{n\geq 0} \frac 1 {n!} X^ n\in \mathbb Q [[X]]$$ and $$\log(1+X) =\sum_{n\geq 1} \frac {(-1)^{n-1}}{n} X^n\in \mathbb Q [[X]].$$
The composition of formal power series $f =\sum_{n\geq 0} a_n X^n$ and $g=\sum_{n\geq 1} b_n X^ n$ is defined as follows: For $k\geq 0$ the power series $g^k = \sum_l c_{k,l} X^ l$ is given by the Cauchy product. Note that $c_{k,l}=0$ if $k>l$ since $b_0=0$. Now $$f\circ g(X)=f(g(X)) := \sum_k a_k \sum_l c_{k,l} X^ l =  \sum _l \left(\sum_{k=0}^l a_k c_{k,l}\right) X^l.$$ How can I see that $\exp(\log(1+X))=1+X$ as formal power series only using reordering of terms?
I'm also interested in the other composition $\log(\exp(X))=X$ where $\log(\exp(X)=\log (1 + (\exp(X)-1))$ which is well-defined since the power series $\exp(X)-1$ has vanishing absolute term.
 A: I found this solution by modifying episqrt163's excellent answer giving a formal power series proof of $\exp(\log(\frac1{1-x}))=\frac1{1-x}$.
\begin{align}
\exp(\log(1+x))
  &=\sum_{k\ge 0}\frac{1}{k!}\Big(\log(1+x)\Big)^k
\\&=\sum_{k\ge 0}\frac1{k!}\left(\sum_{i_1\ge 1}\frac{(-1)^{i_1-1}x^{i_1}}{i_1}\right)\cdots\left(\sum_{i_k\ge 1}\frac{(-1)^{i_k-1}x^{i_k}}{i_k}\right)
\\&=\sum_{k\ge 0}\frac1{k!}\sum_{n\ge k}\;
x^n\sum_{\substack{i_1+\dots+i_k=n \\ i_1\ge 1,\dots,i_k\ge 1}}
\frac{(-1)^{(i_1-1)+\dots+(i_k-1)}}{i_1 i_2\cdots i_k}
\\&=\sum_{n\ge 0}x^n\sum_{k=0}^n\frac1{k!}\sum_{\substack{i_1+\dots+i_k=n \\ i_1\ge 1,\dots,i_k\ge 1}}\frac{(-1)^{n-k}}{i_1 i_2\cdots i_k}
\end{align}
The innermost ranges over compositions of $n$ with exactly $k$ parts. To simplify this unwieldy summation, we will group together all compositions which correspond to the same unordered integer partition.
Let $\lambda=(\lambda_1,\lambda_2,\dots,\lambda_k)$ be an integer partition of $n$ with exactly $k$ parts. Furthermore, define the multiplicity vector $(m_1,\dots,m_n)$ for $\lambda$, where for each $i\in \{1,\dots,n\}$, $m_i$ is the number of parts equal to $i$ in $\lambda$. The number of ordered compositions $(i_1,\dots,i_k)$ corresponding to $\lambda$ when put in sorted order is
$$
\frac{k!}{m_1!\cdots m_n!}
$$
This implies that we can re-index the summation to range over integer compositions $\lambda$ of $n$ with $k$ parts, as follows:
$$
\begin{align}
\exp(\log(1+x))
  &= \sum_{n\ge 0}x^n\sum_{k=0}^n\frac1{k!}(-1)^{n-k}
\sum_{\substack{\lambda \,\vdash n \\ \text{len}(\lambda)=k}}
\frac{k!}{m_1!\cdots m_n!}\frac{1}{1^{m_1}\cdots n^{m_n}}
\\&= \sum_{n\ge 0}\frac{x^n}{n!}\sum_{k=0}^n (-1)^{n-k}
\sum_{\substack{\lambda \,\vdash n \\ \text{len}(\lambda)=k}}
\frac{n!}{m_1!1^{m_1}\cdots m_n!n^{m_n}}
\end{align}
$$
It is well known that $\frac{n!}{m_1!1^{m_1}\cdots m_n!n^{m_n}}$ is equal to the number of permutations with cycle type $\lambda$. Since we are summing over all $\lambda$ with $k$ parts, the innermost sum equals the number of permutations with exactly $k$ cycles, i.e. the unsigned Stirling number of the first kind. That is,
$$
\exp(\log(1+x))=\sum_{n\ge 0}\frac{x^n}{n!}\sum_{k=0}^n (-1)^{n-k}{n \brack k}
$$
Finally, the alternating sum $\sum_{k=0}^n (-1)^{n-k}{n \brack k}$ is equal to zero for all $n\ge 2$, because it computes the difference between the number of permutations with an even number of cycles and the number of permutations with an  odd number of cycles. There is a bijection between these two groups, namely, multiplying by any transposition. The exception is $n=0$ and $n=1$, where $n$ is too small for a transposition to exists. In these cases, the difference is one. This exactly corresponds to the series
$$
1+x+\color{gray}{0x^2+0x^3+\dots},
$$
completing the proof.
A: Here is a mixed proof where we use some combinatorics. Using
combinatorial classes as in Analytic Combinatorics by Flajolet and
Sedgewick we have the following class $\mathcal{P}$  of
permutations:
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}
\mathcal{P} = \textsc{SET}(\textsc{CYC}_{\ge 1}(\mathcal{Z})).$$
This says that permutations are sets of cycles (labeled enumeration).
Translating to EGFs we find
$$\frac{1}{1-z} = \exp \log\frac{1}{1-z}.$$
We seek $\frac{1}{1-z} = 1 + X$ which means we must FPS-substitute $z=X/(1+X)$
which is legal because there is no constant term in $X.$ We get
$$1+X = \exp\log(1+X).$$
We also have                                                                                                                             $$[X^0] \frac{1}{1-X/(1+X)} = 1$$                                                                                                                                 as well as for $n\ge 1$ $$[X^n] \frac{1}{1-X/(1+X)} =                                                    \sum_{q=1}^n [X^n] \frac{X^q}{(1+X)^q}                                           = \sum_{q=1}^n [X^{n-q}] \frac{1}{(1+X)^q}                                       \\ = \sum_{q=1}^n (-1)^{n-q} {n-1\choose q-1}                                    = (-1)^{n-1} \sum_{q=0}^{n-1} (-1)^q {n-1\choose q}                              = (-1)^{n-1} [[n=1]]$$                                                                                                                                            so we only have two non-zero terms, which are, $1+X.$
The above encapsulates the argument by Mike Earnest.
Remark. We can also prove equality of the two logarithmic terms
under the substitution. The labeled cycle EGF yields
$$\log\frac{1}{1-z} = \sum_{q\ge 1} \frac{z^q}{q}.$$
Do the substitution to get
$$\sum_{q\ge 1} \frac{1}{q} \frac{X^q}{(1+X)^q}.$$
What is the coefficient on $[X^n]$ (constant coefficient is zero)?
$$\sum_{q=1}^n \frac{1}{q} [X^{n-q}] \frac{1}{(1+X)^q}
= \sum_{q=1}^n \frac{(-1)^{n-q}}{q} {n-1\choose q-1}
\\ = \frac{(-1)^n}{n} \sum_{q=1}^n (-1)^q {n\choose q}
= \frac{(-1)^{n-1}}{n}.$$
This is precisely the definition that was given by OP.
We also have that the labeled set EGF is
$$\exp(z) = \sum_{q\ge 0} \frac{z^q}{q!}$$
because there is one set containing $q$ labeled elements.
A: Not an answer, but longer than a comment:
You could consider formal power series with a parameter
$$\exp_t(x) = (1+t x)^{\frac{1}{t}}$$
and
$$\log_t(1+x) = \frac{(1+x)^t - 1}{t}$$
and check that
$$\exp_t( \log_t(1+x)) = 1+x$$
(formally), so true for $t=0$ also.  What gives?  We are using
$$((1+x)^t)^{\frac{1}{t}} = 1+x$$
a composition of power series.  So perhaps one should also elucidate
$$((1+x)^a)^b = (1+x)^{a\cdot b}$$
$\bf{Added:}$ The above composition of series is equivalent to the equality
$$\sum_{m_1 + 2 m_2 + 3 m_3 + \cdots = n} \frac{(\sum_{i\ge 1} m_i)!}{\prod_{i\ge 1} m_i!} \binom{b}{\sum_i m_i} \prod_{i\ge 1} \binom{a}{i}^{m_i} = \binom{a b}{n}$$
