# Use of everywhere divergent generating functions

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

-
It's not clear for me which applications do you have in mind. Say, GFs are a powerful tool to manipulate counting sequences. You can solve equations with GFs as with usual function, square root them, use Lgrange inversion formula. Sometimes you can even solve differential equations with genuinely formal series, as variation of constants formula works. For some sequences even the EGF is divergent, the most illustrative examples are graph sequences. Take a look at page 138 of Flajolet and Sedgewick /Analytic Combinatorics/ about enumeration of connected graphs. –  zhoraster Nov 12 '10 at 11:36
Your formal power series reminds me of the Cantor Expansion of an integer; so perhaps there are applications lurking .... –  Suvrit Nov 12 '10 at 13:39
li(x) is the product of x and an everywhere divergent power series in 1/log(x) (in the sense of asymptotic expansion). –  paul Monsky Nov 12 '10 at 14:10
@zhoraster: I mean rather some applications for combinatorial identities or inequalities (say, proving formula for Catalan numbers or some identities for partitions). Of course, highly increasing sequences have divergent GF's and even EGF's, but do such divergent functions, considered as formal power series, help to prove any nontrivial facts about them? –  Fedor Petrov Nov 12 '10 at 19:18

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.

-

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

-

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

-
Thanks for this nice reference! But would you please specify, if I may ask, the place, in which concrete divergent functions occur therein? –  Fedor Petrov Nov 12 '10 at 19:15

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.

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).

-
Oh, thanks for this example, that's almost what I am searching for! But in Exercise 32, this function just appears. Can we derive any non-trivial identity for permutations using this relation and those functions? –  Fedor Petrov Nov 12 '10 at 19:23
Hi Fedor; sorry, not off-the-top of my head. I'll have to check Comtet's book in the library to see what more he points out to. Some more googling related to Comtet shows up several papers. You might benefit from chasing papers that cite Comtet's paper: Comtet, L., Sur les coefficients de l'inverse de la série formelle Σn!tn. C. R. Acad. Sci. Paris Ser. A. v275. 569-572. –  Suvrit Nov 12 '10 at 19:35

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).

-