Use of everywhere divergent generating functions

Question

Generating functions are well-known to be much useful in combinatorics. But, maybe just since I am illiteral, all the applications coming in mind deal with power series, which are not just formal, but have non-zero radius of convergence. So, for sequences of super-exponential growth exponential generating functions $\sum a_nx^n/n!$ are considered, which already converge somewhere, and so on. But for considering formal power series, when we do not use analysis features (sometimes we use, but often do not), convergence is not necessary, and looks like a "coincidence".

Here comes the question: are there any less or more nice and natural application of formal power series like $\sum n! x^n$, which converge only for $x=0$?

Answer 1

Formal power series with radius of convergence 0 often arise in counting labeled graphs. For example, the exponential generating function for labeled connected graphs is $\log G(x)$, where $$G(x) = \sum_{n=0}^\infty 2^{\binom{n}{2}} \frac{x^n}{n!},$$ which has radius of convergence 0.

As Aaron noted, series like $\sum_{n=0}^\infty n! x^n$ arise in the theory of continued fractions; this series has the continued fraction expansions $$ \frac{1}{1-\displaystyle\frac{\mathstrut x}{1- \displaystyle\frac{\mathstrut x}{1- \displaystyle\frac{\mathstrut 2x}{1- \displaystyle\frac{\mathstrut 2x}{1- \displaystyle\frac{\mathstrut 3x}{1- \displaystyle\frac{\mathstrut 3x}{1-\cdots }}}}}}} $$ and $$ \frac{1}{1-x-\displaystyle\frac{\mathstrut x^2}{1- 3x - \displaystyle\frac{\mathstrut 2^2x^2}{1-5x - \displaystyle\frac{\mathstrut 3^2x^2}{1-7x -\cdots }}}} $$

Similar continued fractions exist for ordinary generating functions (with radius of convergence 0) for Bell numbers, Eulerian polynomials, matchings, and more generally, moments of orthogonal polynomials. A very nice combinatorial approach to these continued fractions has been given by Philippe Flajolet, Combinatorial aspects of continued fractions.

It is true that most, if not all, of these examples of nonconverging power series can be refined to power series in more than one variable that do converge for some values of the parameters. For example, the exponential generating function for labeled connected graphs by edges is $\log G(x,t)$, where $$G(x,t) = \sum_{n=0}^\infty (1+t)^{\binom{n}{2}} \frac{x^n}{n!};$$ this converges for $|1+t|<1$. On the other hand, the exponential generating function for strongly connected tournaments is $1-1/G(x)$, and this doesn't seem to generalize since $1-1/G(x,t)$ has some negative coefficients.

Answer 2

In Section 5 of E. A. Bender, Asymptotic methods in enumeration, SIAM Review 16 (1974), 485-515, there is a discussion of the rate of growth of the coefficients of generating functions with zero radius of convergence

Answer 3

The question uses the textbook example of a series with radius of convergence 0: $$f=\sum n!x^n \qquad (1)$$ I am going to take the question as :" Is this $f$ of any use?" A use would be to prove some identity about factorials. One which comes to mind is $$1+\sum_1^{n}(k-1)(k-1)!=n! \qquad (*)$$ To misquotes Samuel Johnson: "Proving (*) using (1) is like a dog walking on it's hinder legs. It is not done well; but you are surprised to find it done at all." Actually I think there is some value to this exercise (but if there is, I need to digress a bit and go a bit slow on a few details to derive it.) Let me first give two other brief proofs.

I like counting proofs. Consider the $n!$ permutations of the positive integers up to $n$. Except for the identity (that's 1), each has a greatest number which is not mapped to itself $m(\sigma)=\max\{j : \sigma(j) \ne j\}$ . So $2\le m(\sigma)\le n$ and the number of permutations with $m(\sigma)=k$ is $(k-1)(k-1)!$. QED

The standard proof of (*) would probably be by induction using the identity $$n!=n\cdot (n-1)!=1\cdot(n-1)!+(n-1)(n-1)! \qquad(2)$$ for the induction step.

So what about using $f$ to prove the identity? $$x^2f'=\sum_0^{\infty}k\cdot k!x^{k+1}=\sum_1^{\infty}(k-1)(k-1)!x^k$$ and $g=\frac{1}{1-x}=\sum_0^{\infty} x^k$. So we need to show that $$f=\frac{1}{1-x}+\frac{1}{1-x}x^2f'\qquad(?)$$ (the first use of $g$ for the $+1$ and the second to sum $(k-1)(k-1)!\ $ ).

One way to do this is: $$xf=\sum_0^{\infty} n!x^{n+1}=\sum_1^{\infty} (n-1)!x^{n}$$ So differentiating directly: $$(xf)'=\sum_1^{\infty} n\cdot (n-1)!x^{n-1}=\sum_1^{\infty} n!x^{n-1} \qquad(4)$$ And hence $$1+x\cdot(xf)'=f \qquad(5)$$ But using the product rule, $$(xf)'=f+xf' \qquad(6)$$ Substituting (6) in (5), $$1+xf+x^2f'=f$$ and a little manipulation gives (?) as desired.

So how different are the three proofs? The identity (2) in the inductive proof might be justified as part of the inductive definition of $n!$ or as part of the counting proof that $|S_n|=(1+(n-1))|S_{n-1}|$ because each $\sigma \in S_n$ either fixes $n$ or does not. If you buy that, then the first proof is just the repeated application of this identity. And what did we use, if not convergence, for the generating function proof? The powers of $x$ just kept things in order. One important step was (4) where we used the identity (2).

For fancier uses, this article Notes on Euler’s work on divergent factorial series and their associated continued fractions says that Euler called the alternating form of $f$ the divergent series par excellence and takes it from there (There might be better articles to quote).

Answer 4

Actually, I found a nice example of such a function in Stanley's classic: Enumerative Combinatorics, Volume I, on page 49, Exercise 32, which asks the reader to analyze the number of indecomposable permutation, and permutations with no strong fixed-point.

Please look here: Exercise 32

I am sure, there are several other natural examples where such generating functions show up. For example, later on page 61 Stanley cites Comtet's Advanced combinatorics, wherein, this generating function of yours is called an Euler formal series

I guess, given these two starting points, one can find more examples where these formal series show up (perhaps also in Henrici's book, but I haven't checked).

Answer 5

All questions[*] are answered in the book: generatingfunctionology by Wilf. First edition available free on the internet:
http://www.math.upenn.edu/~wilf/DownldGF.html
Note that convergence of the generating function is unnecessary except in one chapter.

[*]A slight exaggeration...