44
$\begingroup$

Consider the following two generating functions: $$e^x=\sum_{n=0}^{\infty}\frac{x^n}{n!}$$ $$\log\left(\frac{1}{1-x}\right)=\sum_{n=1}^{\infty}\frac{x^n}{n}.$$ If we live in function-land, it's clear enough that there is an inverse relationship between these two things. In particular, $$e^{\log\left(\frac{1}{1-x}\right)}=1+x+x^2+x^3+\ldots$$ If we live in generating-function-land, this identity is really not so obvious. We can figure out that the coefficient of $x^n$ in $e^{\log\left(\frac{1}{1-x}\right)}$ is given as $$\sum_{a_1+\ldots+a_k=n}\frac{1}{a_1\cdot \cdots \cdot a_k}\cdot \frac{1}{k!}$$ where the sum runs over all ways to write $n$ as an ordered sum of positive integers. Supposedly, for each choice of $n$, this thing sums to $1$. I really don't see why. Is there a combinatorial argument that establishes this?

$\endgroup$
5
  • 8
    $\begingroup$ This seems like a nice example of the old joke that $\pi_1(\text{mathematics})$ is non-trivial. There are two different ways to prove this equality of composition of power series "from scratch" and it really seems the analytic proof is genuinely different, i.e. never uses the combinatorial identity in a hidden way. $\endgroup$ – hunter Aug 17 '19 at 15:53
  • $\begingroup$ What is your question? Are you looking for a proof by the method of computing the composition of two different power series because you want to know how to prove it by that method and not just how to prove it using the fact that $e^{\log(\frac{1}{1 - x})} = \frac{1}{1 - x}$ when ever $e^{\log(\frac{1}{1 - x})}$ is defined? $\endgroup$ – Timothy Aug 17 '19 at 21:34
  • $\begingroup$ @hunter: Sorry I don't understand your comment. Every proof of the fact has to pass through the identity $\exp(x) = \sum_{k=0}^∞ \frac{x^k}{k!}$. Whether or not it is a definition or a theorem, one has to prove something non-trivial, and that is where the combinatorics is hiding. $\endgroup$ – user21820 Aug 18 '19 at 2:37
  • $\begingroup$ @hunter "the old joke that $\pi_1$(mathematics) is non-trivial". I like mathematical jokes ; I don't know this one. Any pointer ? $\endgroup$ – Jean Marie Aug 18 '19 at 8:42
  • 2
    $\begingroup$ I asked the analogous question for the composition $\log \exp x = x$ here: math.stackexchange.com/q/3326729/70202. $\endgroup$ – Mark Wildon Aug 18 '19 at 9:40
20
$\begingroup$

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!$.

$\endgroup$
0
16
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.