12
$\begingroup$

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

$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$
    – zhoraster
    Nov 12, 2010 at 11:36
  • $\begingroup$ Your formal power series reminds me of the Cantor Expansion of an integer; so perhaps there are applications lurking .... $\endgroup$
    – Suvrit
    Nov 12, 2010 at 13:39
  • 3
    $\begingroup$ li(x) is the product of x and an everywhere divergent power series in 1/log(x) (in the sense of asymptotic expansion). $\endgroup$ Nov 12, 2010 at 14:10
  • $\begingroup$ @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? $\endgroup$ Nov 12, 2010 at 19:18
  • $\begingroup$ Not sure about the generating function part, but there was this really humorous evaluation at a finite point of an asymptotic series that actually worked to deduce ((even) if not prove, which would probably take quite some effort) something. My memory was unfortunately too small to contain it, but it was at least as hilarious and good as the zeta-function joke (not the Ramanujan one; can't remember this either). $\endgroup$ Dec 15, 2015 at 1:25

5 Answers 5

15
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

$\endgroup$
1
5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Nov 12, 2010 at 19:23
  • $\begingroup$ 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. $\endgroup$
    – Suvrit
    Nov 12, 2010 at 19:35
4
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ Thanks for this nice reference! But would you please specify, if I may ask, the place, in which concrete divergent functions occur therein? $\endgroup$ Nov 12, 2010 at 19:15
  • $\begingroup$ See also mathoverflow.net/a/419679/454 $\endgroup$ Oct 17, 2022 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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