Combinatorial Argument for Exponential and Logarithmic Function Being Inverse

In your sum, you are distinguishing between the same collection of numbers when it occurs in different orders. So you'll have separate summands for $(a_1,a_2,a_3,a_4)=(3,1,2,1)$, $(2,3,1,1)$, $(1,1,3,2)$ etc.

Given a multiset of $k$ numbers adding to $n$ consisting of $t_1$ instances of $b_1$ up to $t_j$ instances of $b_j$, that contributes $$\frac{k!}{t_1!\cdot\cdots\cdot t_j!}$$ (a multinomial coefficient) summands to the sum, and so an overall contribution of $$\frac{1}{t_1!b_1^{t_1}\cdot\cdots\cdot t_j!b_j^{t_j}}$$ to the sum. But that $1/n!$ times the number of permutations with cycle structure $b_1^{t_1}\cdot\cdots\cdots b_j^{t_j}$. So this identity states that the total number of permutations of $n$ objects is $n!$.


In brief, $n!$ times the summand in the sum you write down is equal to the number of permutations on $n$ symbols that decompose into the product of disjoint cycles of lengths $a_1,\dots,a_k$. More precisely, this is true if you combine all of the terms in the sum corresponding to the same multiset $\{a_1,\dots,a_k\}$.

See exercises 10.2 and 10.3 of these notes for related material.


This answer really just consists of remarks on the already given answers, to this question and the related one here:

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

Remark 1. Let two functions $f(x)$, $g(y)$, $f(0) = 0$, $g(0) = 0$ be mutually inverse with respect to substitution, that is, $f(g(y)) = y$, $g(f(x)) = x$. The chain rule then give$$1 = (f(g(y)))' = f'(g(y))g'(y), \quad 1 = (g(f(x)))' = g'(f(x))f'(x),$$where in each case prime denotes the derivative denotes the derivative taken with respect to the corresponding argument. Conversely, if two generating functions $f$ and $g$ with vanishing constant terms satisfy these equalities, then they are mutually inverse with respect to substitution.

In particular, for the exponent and the logarithm, we expect to have two mutually inverse with respect to substitution functions, namely, $f(x) = e^x - 1$, and $g(y)= \log(1 + y)$ (the shift in both cases aims at making the free term vanishing). Note that $f'(x) = e^x$ and$$\begin{align} (\log(1 + y))' & = \left(y - {{y^2}\over2} + {{y^3}\over3} - \ldots\right)' \\ & = 1 - y + y^2 - y^3 + \ldots \\ & = {1\over{1 + y}}.\end{align}$$Now, check$$\begin{align} (\log(e^x))' & = (\log(1 + (e^x - 1)))' \\ & = {1\over{1 + (e^x - 1)}}e^x \\ & = 1,\end{align}$$as required.

Remark 2. First, if we are familiar with the combinatorial interpretation of exponential generating functions, especially composition of exponential generating functions, as explained, for example, in Chapter 5 of Richard Stanley's Enumerative Combinatorics: Volume 2 then we do not need to write out the sums over compositions: we can see directly that $\exp(\log(1/(1-x)))$ counts sets of cycles, which may be viewed as permutations, and that $\exp(\log(1-x))$ counts sets of cycles where each set of cycles is weighted by $(-1)^{\# \text{ of cycles}}$. There is a simple bijection between permutations with an even number of cycles and with an odd number of cycles: just multiply a permutation by any fixed odd permutation.

For the other way around, the theory of exponential generating functions tells us that$$\log(e^x) = \log(1+ (e^x-1))$$counts cycles of nonempty sets, where the weight of a cycle of $k$ nonempty sets is $(-1)^{k-1}$. It is easy to see how these cycles of nonempty sets correspond to our surjective functions with $f(1)=1$, but again, we do not need to write out a sum of compositions. Our bijection can be restated in terms of cycles of nonempty sets in a simple way (though describing this more formally will take longer): If $1$ is in a singleton set, push it back into the preceding set, and if $1$ is not in a singleton set, push it forward into a new singleton set.

Remark 3. Here are few other ways to look at the inverse relationship between $\log(1+x)$ and $e^x -1$.

  1. The Möbius function of the lattice of partitions of $\{1,\ldots, n\}$ is $(n-1)!$. See http://math.mit.edu/~rstan/pubs/pubfiles/10.pdf, Example 5.5.

  2. The duality between Stirling numbers of the first and second kinds. See https://en.wikipedia.org/wiki/Stirling_number (the section "As inverse matrices").

  3. Brian Drake proved a theorem that explains combinatorially many pairs of inverse exponential generating functions. See An inversion theorem for labeled trees and some limits of areas under lattice paths, Example 1.4.2.