Let's there be two exponential generating functions:
$A(x)=\sum^\infty_{n=1}\frac{a_n}{n!}x^n$
$B(x)=\sum^\infty_{n=1}\frac{b_n}{n!}x^n$
Sequence ${\{a_n\}}^\infty_{n=1}$ defines number of all possible simple graphs on n labelled vertices.
Sequence ${\{b_n\}}^\infty_{n=1}$ defines number of all possible simple connected graphs on n labelled vertices.
I am trying to prove the following relationship between these two generating functions:
$A(x)=e^{B(x)}-1$
The expression for $a_n$ is easy to derive: $a_n=2^{\frac{n(n-1)}{2}}$, but I don't know how to demonstrate the equation above.
I found the following hint for this problem:
It can be shown that $\frac{(B(x))^k}{k!}$ is the exponential generating series for the labelled graph with exactly k components.
2026-03-29 22:34:37.1774823677
Proving relation between exponential generating functions whose coefficients count certain types of graphs
167 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
A further HINT: The hint tells you that
$$e^{B(x)}=\sum_{k\ge 0}\frac{\big(B(x)\big)^k}{k!}\,,$$
so
$$e^{B(x)}-1=\sum_{k\ge 1}\frac{\big(B(x)\big)^k}{k!}\,.$$
A simple graph on $n$ vertices has at least one component, so . . .
You may find Problem $413$ of this web page or Section $4$ of this PDF helpful.