Combinatorial proof that the exponential and logarithmic functions are inverse, the other way around

436 Views Asked by At

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$?

1

There are 1 best solutions below

2
On 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.