In the spirit of Combinatorial Argument for Exponential and Logarithmic Function Being Inverse, is there a combinatorial proof that $\exp$ and $\log$ are inverse, evaluating the composition the other way around?
More precisely, since $\log (1+x) = \sum_{k=1}^\infty \frac{(-1)^{k-1}}{k} x^k$ for $|x| < 1$ and $\exp x = 1+ \sum_{m=1}^\infty \frac{1}{m!} x^m$, the coefficient of $x^n$ in $\log \exp x$ is
$$\sum_{a_1+\cdots + a_k = n} \frac{(-1)^{k-1}}{a_1! \ldots a_k! k} $$
where, as in the linked question, the sum is over all ways to write $n$ as an ordered sum $a_1 + \cdots + a_k$ of strictly positive integers. It's clear the coefficient is $1$ when $n=1$, since the only summand is $(-1)^0/1 = 1$.
Is there a combinatorial proof that this coefficient is $0$ unless $n=1$?
Best Answer
Note that $\frac{n!}{a_1!a_2!\ldots a_k!}$ counts the number of functions $f:\{1,\ldots,n\}\rightarrow \{1,\ldots,k\}$ such that there are $a_i$ elements mapping to $i$ - it can be understood as the multinomial coefficient ${n \choose a_1,a_2,\ldots,a_k}$. Then, if we fix some $k$ and sum this quantity up over all possible decompositions $a_1+\ldots+a_k=n$, we are counting the number of surjective functions from $\{1,\ldots,n\}$ to $\{1,\ldots, k\}$. A proportion of $1/k$ of these maps have the property that $f(1)=1$.
For any $n$ and $k$ let $S_{n\rightarrow k}$ be the set of surjective functions $f:\{1,\ldots,n\}\rightarrow \{1,\ldots,k\}$ such that $f(1)=1$. Observe that $$|S_{n\rightarrow k}|=\frac{n!}k\cdot \sum_{a_1+\ldots+a_k=n}\frac{1}{a_1!a_2!\ldots a_k!}$$ Let $S_{n\rightarrow\text{even}}$ be the union of $S_{n\rightarrow k}$ over all even $k$ and $S_{n\rightarrow\text{odd}}$ be the union of $S_{n\rightarrow k}$ over all odd $k$. We claim that if $n\geq 2$ then $S_{n\rightarrow\text{even}}$ and $S_{n\rightarrow\text{odd}}$ are equally large. To do this, we define an involution on $S_{n\rightarrow\text{even}}\cup S_{n\rightarrow\text{odd}}$ that changes the parity of each function.
In particular, let $f$ be a surjection from $\{1,\ldots,n\}$ to some $\{1,\ldots, k\}$ such that $f(1)=1$. We will define a new surjection $f'$ from $\{1,\ldots,n\}$ to some other $\{1,\ldots,k'\}$ where $k'$ is either $k+1$ or $k-1$.
We do this definition in two steps: If there is some $i$ other than $1$ such that $f(i)=1$, we define $$f'(x)=\begin{cases}1 & \text{if }x=1\\ k+1 & \text{if }x\neq 1 \text{ and }f(x)=1\\ f(x) & \text{otherwise.} \end{cases}$$ This essentially takes the preimage of $1$ under $f$ and throws everything except $1$ to a new image. This is a surjection to $\{1,\ldots,k+1\}$.
Otherwise, if the preimage of $1$ under $f$ is just $\{1\}$, we will take the things that were mapped to $k$ and map them to $1$ instead. Formally, we define $$f'(x)=\begin{cases}1 & \text{if }x=1 \text{ or }f(x)=k\\ f(x) & \text{otherwise.} \end{cases}$$ We can see that $f''=f$ and that $f'$ has the opposite parity from $f$. Thus the map taking $f$ to $f'$ is a bijection between $S_{n\rightarrow\text{even}}$ and $S_{n\rightarrow\text{odd}}$. Expanding this, we can write an equation: $$\sum_{k=1}^n (-1)^k|S_{n\rightarrow k}| = 0$$ and then, by dividing out by $n!$ and negating this and substituting in our expression for $|S_{n\rightarrow k}|$, we get the desired identity.