Convergence of Exponential Generating Functions

192 Views Asked by At

In page 10 of "Enumerative Combinatorics by Stanley, volume 2", let $h(n)=2^{n \choose 2}$ be the number of graphs on an $n$-element vertex set $S$. And let $c(n)$ be the number of connected graphs on the vertex set $S$. So using the exponential formula of generating functions,

$$E_{h}(x)=\sum_{n\geq 0} 2^{n \choose 2} \frac{x^n}{n!}=\text{exp}E_{c}(x)=\text{exp}\sum_{n\geq1}c(n)\frac{x^n}{n!}.$$

The book says both $E_{h}(x)$ and $E_{c}(x)$ have zero radius of convergence. What's the use of the above formula??

In other words, if we have an equality of two exponential generating functions with zero radius of convergence, can we conclude that corresponding coefficients are equal?

1

There are 1 best solutions below

0
On

To your question "what is the use of the above formula?", you can use this to calculate $c(n)$. $$ E_h(x) = \exp E_c(x)\implies E_h'(x)=E_c'(x)E_h(x) $$ which implies that $$ h(n+1) = \sum_{k=0}^n\binom{n}kc(k+1)h(n-k) $$ Rewriting this slightly, $$ c(n+1) = h(n+1) - \sum_{k=0}^{n-1}\binom{n}kc(k+1)h(n-k) $$ This allows you to recursively compute $c(n+1)$ using the easily computable $h(n-k)$ and the previously computed values of $c(k+1)$.