0
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ The equality sign is sayin that the coefficients are equal. The remark that the radius of convergence is 0 is merely an aside. $\endgroup$ – Morgan Rodgers Jan 14 '19 at 1:47
  • $\begingroup$ So if we have $\sum a_n \frac{x^n}{n!}=\sum b_n \frac{x^n}{n!}$ with zero radius of convergence, can we conclude that $a_n=b_n$? $\endgroup$ – S_Alex Jan 14 '19 at 2:29
  • 3
    $\begingroup$ Since $x$ is an indeterminate, the equal sign means that all the coefficients are the same. These are formal series; we are not concerned with convergence. $\endgroup$ – Morgan Rodgers Jan 14 '19 at 2:47
1
$\begingroup$

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

$\endgroup$

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.