I recently came across the following in something I'm working on, and I'd never seen it before. Consider \begin{align*} f_1(x) &= (1+x)^{1/1} \\\ f_2(x) &= (1+x)^{2/1} (1+2x)^{-1/2} \\\ f_3(x) &= (1+x)^{3/1} (1+2x)^{-3/2} (1+3x)^{1/3} \\\ f_4(x) &= (1+x)^{4/1} (1+2x)^{-6/2} (1+3x)^{4/3} (1+4x)^{-1/4} \\\ & \cdots \\\ f_n(x) &= \prod_{k=1}^n (1+kx)^{(-1)^{k-1}\binom{n}{k}/k}. \end{align*} Think of these as formal power series with coefficients in $\mathbb{Q}$. It turns out that these series approximate the Taylor expansion for the exponential, in the sense that $$ f_n(x) = 1 + x + \frac{x^2}{2!} + \cdots + \frac{x^n}{n!} +O(x^{n+1}).$$

(This isn't too hard to prove, using a logarithmic derivative: \begin{align*} 1-f_n'(x)/f_n(x) &= \sum_{k=0}^n (-1)^k\binom{n}{k}(1+kx)^{-1} \\\ &= \sum_j \biggl(\sum_k (-1)^k\binom{n}{k}k^j\biggr) (-x)^j. \end{align*} The coefficient of $x^j$ calculates the number of surjections $\{1,\dots,j\}\to \{1,\dots,n\}$ (up to a sign), and so is $0$ if $j<n$.)

My questions include (but are not limited to): Do these things have a name? Is there some kind of combinatorial interpretation of the $f_n(x)$ (e.g., as a generating function of some kind)? Is there a more direct proof that $f_n(x)$ agrees with $e^x$ to order $n+1$?

  • 4
    $\begingroup$ The vanishing of the inner sum $\sum_k (-1)^k\binom{n}{k}k^j$ for $0 \leq j < n$ can also be seen by interpreting it as the $n$-th finite difference of a polynomial of degree less than $n$. $\endgroup$ – Noam D. Elkies Nov 21 '11 at 2:29

I'm going to switch a couple of signs and focus on $g_n(x)=\frac{1}{f_n(-x)}$ for a moment. It is an exponential generating function for the number of properly $n$-colored rooted monotonic planar forests of depth at most $1$.

I should clarify that by "$n$-colored" I mean that each edge is assigned one of given $n$ colors, and by "properly $n$-colored" I mean $n$-colored with the property that or any pair $i,j$, any edge with color $i$ is adjacent to some edge of color $j$. A monotonic rooted tree is a labelled tree for which the label of a vertex is greater than the labels of its children. It is now clear that $g_n(x)$ agrees with $e^x$ up to order $n$, since the only $g$-structures of order up to $n$ are graphs with no edges (if there were any edges, "properly $n$ colored" needs at least $n+1$ vertices).

It remains to see why the generating function of these structures is what it is. Combinatorial species give a nice framework for interpreting combinatorially what different operations on the generating function mean at the level of objects being counted. Here is a sketch:

Exponential Generating function for labelled monotonic planar rooted trees of depth at most 1 is $\log(1-x)$.

Therefore the EGF for $k$-colored labelled monotonic planar rooted trees of depth at most 1 is $\frac{1}{k}\log(1-kx)$.

The binomial tranform of order $n$ changes "$k$-colored" to "properly $n$-colored".

The exponential formula changes "tree" to "forest".

So this all gives $$g_n(x)=\exp\left(\sum_{k=1}^n (-1)^k\binom{n}{k}\frac{1}{k}\log(1-kx)\right)$$

| cite | improve this answer | |
  • $\begingroup$ Nice! "Forests of depth at most one" is a bit of an awkward idea for me; could we re-express this as counting some kind of partitions of something? $\endgroup$ – Charles Rezk Nov 22 '11 at 22:28

See A019538, A049019, and A133314 for extensive formula for the coefficients and relation to face vectors of permutahedra/permutohedra. Your proof is a nice one in that A133314 clearly shows why the lower order coefficients as given by the finite differences must vanish if $1/f_n(x)$ truly is an approximation of $exp(-x)$.

| cite | improve this answer | |

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.