Mixing
Generating function for the number of graphs with $k$ connected components
$begingroup$
There are $$b_n = frac{(n-1)!}{2}$$ ways to form a cycle on $n$ labelled vertices, for $ngeq 3$. The exponential generating function for this sequence is
$$ f(x) = frac{1}{2}sum_{ngeq 3} (n-1)! frac{x^n}{n!} =frac{1}{2}sum_{ngeq 3} frac{x^n}{n},$$
and if we want the number of graphs on $n$ vertices, the components of which are cycles, the EGF is
$$ g(x) = exp(f(x)) = exp left(frac{1}{2}sum_{ngeq 1} frac{x^n}{n} - frac{x}{2} - frac{x^2}{4}right)$$
$$ =exp left( - frac{x}{2} - frac{x^2}{4}right) (1-x)^{-1/2}.$$
(This is example 5.2.8 in Stanley's Enumerative Combinatorics, Vol II)
I'd like to do a similar thing with the number of connected components in a graph.
Fix $n$ and $m$, and consider the graphs on $n$ labelled vertices, with $m$ edges. (We may assume $mll n$.) Suppose we know there are $C_{j,l}$ ways to get a connected graph on $j$ vertices and $l$ edges. So, in particular, $C_{j,l}=0$ in case $l<j-1$, or $l>binom{j}{2}$.
Question:
Is it feasible to get an EGF for the sequence $a_k$ of the number of graphs with $k$ connected components ?
Clarification:
Let us use the term $(n,m)$-graph, for a graph with $n$ vertices and $m$ edges. We fix $n$ and $m$, and may assume that $mll n$. Now, there are $binom{binom{n}{2}}{m}$ such $(n,m)$-graphs. Let $a_k$ be the number of $(n,m)$-graphs with $k$ connected components. Clearly, $sum_{k=1}^n a_k = binom{binom{n}{2}}{m}$. I'm interested in the EGF
$$ sum_{k=1}^n frac{a_k}{k!} x^k.$$
combinatorics graph-theory generating-functions
asked Jan 31 at 7:55
TeddyTeddy
1,236817
$endgroup$
add a comment |
$begingroup$
There are $$b_n = frac{(n-1)!}{2}$$ ways to form a cycle on $n$ labelled vertices, for $ngeq 3$. The exponential generating function for this sequence is
$$ f(x) = frac{1}{2}sum_{ngeq 3} (n-1)! frac{x^n}{n!} =frac{1}{2}sum_{ngeq 3} frac{x^n}{n},$$
and if we want the number of graphs on $n$ vertices, the components of which are cycles, the EGF is
$$ g(x) = exp(f(x)) = exp left(frac{1}{2}sum_{ngeq 1} frac{x^n}{n} - frac{x}{2} - frac{x^2}{4}right)$$
$$ =exp left( - frac{x}{2} - frac{x^2}{4}right) (1-x)^{-1/2}.$$
(This is example 5.2.8 in Stanley's Enumerative Combinatorics, Vol II)
I'd like to do a similar thing with the number of connected components in a graph.
Fix $n$ and $m$, and consider the graphs on $n$ labelled vertices, with $m$ edges. (We may assume $mll n$.) Suppose we know there are $C_{j,l}$ ways to get a connected graph on $j$ vertices and $l$ edges. So, in particular, $C_{j,l}=0$ in case $l<j-1$, or $l>binom{j}{2}$.
Question:
Is it feasible to get an EGF for the sequence $a_k$ of the number of graphs with $k$ connected components ?
Clarification:
Let us use the term $(n,m)$-graph, for a graph with $n$ vertices and $m$ edges. We fix $n$ and $m$, and may assume that $mll n$. Now, there are $binom{binom{n}{2}}{m}$ such $(n,m)$-graphs. Let $a_k$ be the number of $(n,m)$-graphs with $k$ connected components. Clearly, $sum_{k=1}^n a_k = binom{binom{n}{2}}{m}$. I'm interested in the EGF
$$ sum_{k=1}^n frac{a_k}{k!} x^k.$$
combinatorics graph-theory generating-functions
asked Jan 31 at 7:55
TeddyTeddy
1,236817
$endgroup$
1
$begingroup$
Some material to consult at this MSE link.
$endgroup$
– Marko Riedel
Jan 31 at 15:05
$begingroup$
Can you clarify: $a_k$ is the number of graphs on $n$ vertices with $m$ edges and $k$ components? And you want to find $sum_{k=0}^{n}a_kfrac{x^k}{k!}$?
$endgroup$
– Mike Earnest
Jan 31 at 16:30
$begingroup$
@MikeEarnest Correct.
$endgroup$
– Teddy
Feb 3 at 7:26
add a comment |
$begingroup$
There are $$b_n = frac{(n-1)!}{2}$$ ways to form a cycle on $n$ labelled vertices, for $ngeq 3$. The exponential generating function for this sequence is
$$ f(x) = frac{1}{2}sum_{ngeq 3} (n-1)! frac{x^n}{n!} =frac{1}{2}sum_{ngeq 3} frac{x^n}{n},$$
and if we want the number of graphs on $n$ vertices, the components of which are cycles, the EGF is
$$ g(x) = exp(f(x)) = exp left(frac{1}{2}sum_{ngeq 1} frac{x^n}{n} - frac{x}{2} - frac{x^2}{4}right)$$
$$ =exp left( - frac{x}{2} - frac{x^2}{4}right) (1-x)^{-1/2}.$$
(This is example 5.2.8 in Stanley's Enumerative Combinatorics, Vol II)
I'd like to do a similar thing with the number of connected components in a graph.
Fix $n$ and $m$, and consider the graphs on $n$ labelled vertices, with $m$ edges. (We may assume $mll n$.) Suppose we know there are $C_{j,l}$ ways to get a connected graph on $j$ vertices and $l$ edges. So, in particular, $C_{j,l}=0$ in case $l<j-1$, or $l>binom{j}{2}$.
Question:
Is it feasible to get an EGF for the sequence $a_k$ of the number of graphs with $k$ connected components ?
Clarification:
Let us use the term $(n,m)$-graph, for a graph with $n$ vertices and $m$ edges. We fix $n$ and $m$, and may assume that $mll n$. Now, there are $binom{binom{n}{2}}{m}$ such $(n,m)$-graphs. Let $a_k$ be the number of $(n,m)$-graphs with $k$ connected components. Clearly, $sum_{k=1}^n a_k = binom{binom{n}{2}}{m}$. I'm interested in the EGF
$$ sum_{k=1}^n frac{a_k}{k!} x^k.$$
combinatorics graph-theory generating-functions
asked Jan 31 at 7:55
TeddyTeddy
1,236817
$endgroup$
There are $$b_n = frac{(n-1)!}{2}$$ ways to form a cycle on $n$ labelled vertices, for $ngeq 3$. The exponential generating function for this sequence is
$$ f(x) = frac{1}{2}sum_{ngeq 3} (n-1)! frac{x^n}{n!} =frac{1}{2}sum_{ngeq 3} frac{x^n}{n},$$
and if we want the number of graphs on $n$ vertices, the components of which are cycles, the EGF is
$$ g(x) = exp(f(x)) = exp left(frac{1}{2}sum_{ngeq 1} frac{x^n}{n} - frac{x}{2} - frac{x^2}{4}right)$$
$$ =exp left( - frac{x}{2} - frac{x^2}{4}right) (1-x)^{-1/2}.$$
(This is example 5.2.8 in Stanley's Enumerative Combinatorics, Vol II)
I'd like to do a similar thing with the number of connected components in a graph.
Fix $n$ and $m$, and consider the graphs on $n$ labelled vertices, with $m$ edges. (We may assume $mll n$.) Suppose we know there are $C_{j,l}$ ways to get a connected graph on $j$ vertices and $l$ edges. So, in particular, $C_{j,l}=0$ in case $l<j-1$, or $l>binom{j}{2}$.
Question:
Is it feasible to get an EGF for the sequence $a_k$ of the number of graphs with $k$ connected components ?
Clarification:
Let us use the term $(n,m)$-graph, for a graph with $n$ vertices and $m$ edges. We fix $n$ and $m$, and may assume that $mll n$. Now, there are $binom{binom{n}{2}}{m}$ such $(n,m)$-graphs. Let $a_k$ be the number of $(n,m)$-graphs with $k$ connected components. Clearly, $sum_{k=1}^n a_k = binom{binom{n}{2}}{m}$. I'm interested in the EGF
$$ sum_{k=1}^n frac{a_k}{k!} x^k.$$
combinatorics graph-theory generating-functions
combinatorics graph-theory generating-functions
asked Jan 31 at 7:55
TeddyTeddy
1,236817
asked Jan 31 at 7:55
TeddyTeddy
1,236817
edited Feb 4 at 6:48
Teddy
asked Jan 31 at 7:55
TeddyTeddy
1,236817
asked Jan 31 at 7:55
TeddyTeddy
1,236817
asked Jan 31 at 7:55
TeddyTeddy
1,236817
1,236817
1
$begingroup$
Some material to consult at this MSE link.
$endgroup$
– Marko Riedel
Jan 31 at 15:05
$begingroup$
Can you clarify: $a_k$ is the number of graphs on $n$ vertices with $m$ edges and $k$ components? And you want to find $sum_{k=0}^{n}a_kfrac{x^k}{k!}$?
$endgroup$
– Mike Earnest
Jan 31 at 16:30
$begingroup$
@MikeEarnest Correct.
$endgroup$
– Teddy
Feb 3 at 7:26
add a comment |
1
$begingroup$
Some material to consult at this MSE link.
$endgroup$
– Marko Riedel
Jan 31 at 15:05
$begingroup$
Can you clarify: $a_k$ is the number of graphs on $n$ vertices with $m$ edges and $k$ components? And you want to find $sum_{k=0}^{n}a_kfrac{x^k}{k!}$?
$endgroup$
– Mike Earnest
Jan 31 at 16:30
$begingroup$
@MikeEarnest Correct.
$endgroup$
– Teddy
Feb 3 at 7:26
1
1
$begingroup$
Some material to consult at this MSE link.
$endgroup$
– Marko Riedel
Jan 31 at 15:05
$begingroup$
Some material to consult at this MSE link.
$endgroup$
– Marko Riedel
Jan 31 at 15:05
$begingroup$
Can you clarify: $a_k$ is the number of graphs on $n$ vertices with $m$ edges and $k$ components? And you want to find $sum_{k=0}^{n}a_kfrac{x^k}{k!}$?
$endgroup$
– Mike Earnest
Jan 31 at 16:30
$begingroup$
Can you clarify: $a_k$ is the number of graphs on $n$ vertices with $m$ edges and $k$ components? And you want to find $sum_{k=0}^{n}a_kfrac{x^k}{k!}$?
$endgroup$
– Mike Earnest
Jan 31 at 16:30
$begingroup$
@MikeEarnest Correct.
$endgroup$
– Teddy
Feb 3 at 7:26
$begingroup$
@MikeEarnest Correct.
$endgroup$
– Teddy
Feb 3 at 7:26
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
OP is asking for credible and/or official sources. We cite the Labeled Counting Lemma stated in Graphical Enumeration by F. Harary and E.M. Palmer. This lemma is important since it clarifies the usage of exponential generating functions and the authors just use connected, labeled graphs with $n$ components as demonstration of this lemma.
A theorem in section 1.2 Connected graphs states: The number $C_k$ of connected, labeled graphs with $k$ nodes is
begin{align*}
color{blue}{C_k=2^{binom{k}{2}}-frac{1}{k}sum_{j=1}^{k-1}binom{k}{j}j2^{binom{k-j}{2}}C_j}tag{1}
end{align*}
Let $C(x)$ denote the exponential generating function for the connected, labeled graphs. We find the sequence $(C_k)_{kgeq 0}$ in OEIS as A001187 with generating function
begin{align*}
sum_{k=0}^infty C_kfrac{x^k}{k!}&=1+logleft(sum_{j=0}^infty 2^{binom{j}{2}}frac{x^j}{j!}right)\
&=1+x + frac{x^2}{2!} + 4frac{x^3}{3!} + 38frac{x^4}{4!} + 728frac{x^5}{5!}\
&qquad + 26,704frac{x^6}{6!} + 1,866,256frac{x^7}{7!} + cdots
end{align*}
We start with a motivation for exponential generating functions followed by the labeled counting lemma.
Harary, Palmer: section 1.2
It is important to have at hand the concept of the exponential generating function and some of its associated properties. We shall therefore introduce these functions now ...
For each $k=1,2,3,ldots$, let $a_k$ be the number of ways of labeling all graphs of order $k$ which have some property $P(a)$. Then the formal power series
begin{align*}
a(x)=sum_{k=1}^infty a_kx^k/k!
end{align*}
is called the exponential generating function for the class of graphs at hand. Suppose also that
begin{align*}
b(x)=sum_{k=1}^infty b_kx^k/k!
end{align*}
is another exponential generating function for a class of graphs with property $P(b)$.
The next lemma provides a useful interpretation of the coefficients of the product $a(x)b(x)$ of these two generating functions.
Labeled Counting Lemma: The coefficient of $x^k/k!$ in $a(x)b(x)$ is the number of ordered pairs $(G_1,G_2)$ of two disjoint graphs, where $G_1$ has property $P(a)$, $G_2$ has property $P(b)$, $k$ is the number of points in $G_1cup G_2$ and the labels $1$ through $k$ have been distributed over $G_1cup G_2$.
- To illustrate, let $C(x)$ be the exponential generating functions for labeled, connected graphs,
begin{align*}
C(x)=sum_{k=1}^infty C_k x^k/k!
end{align*}
- Then $C(x)C(x)$ is the generating function for ordered pairs of labeled, connected graphs. On dividing this series by $2$, we have the generating function for labeled graphs which have exactly two components. Similarly $C^n(x)/n!$ has as the coefficient of $x^k/k!$, the number of labeled graphs of order $k$ with exactly $n$ components. If we let $G(x)$ be the exponential generating function for labeled graphs, we then have
begin{align*}
color{blue}{G(x)=sum_{n=1}^infty C^n(x)/n!}tag{2}
end{align*}
The last paragraph together with (2) reveals the connection between labeled, connected graphs and labeled graphs consisting of $n$ components. The authors close this section by presenting the functional equation connecting $G(x)$ with $C(x)$.
Thus we have the following exponential relationship for $G(x)$ and $C(x)$ found by R.J. Riddel [Contributions to the theory of condensation, Dissertation, 1951].
Theorem: The exponential generating function $G(x)$ and $C(x)$ for labeled graphs and labeled connected graphs come to terms in the following relation
begin{align*}
1+G(x)=e^{C(x)}
end{align*}
answered Feb 3 at 21:03
Markus ScheuerMarkus Scheuer
63.8k460152
$endgroup$
$begingroup$
Upvoted. (+1). These are useful references to a classic text.
$endgroup$
– Marko Riedel
Feb 4 at 17:25
add a comment |
$begingroup$
We compute a recurrence for the number of labeled graphs with $k$
components. With $G(z)$ the EGF of labeled graphs we have
$$G(z) = sum_{nge 0} 2^{nchoose 2} frac{z^n}{n!}.$$
Here we have included the empty graph on zero nodes. Now the class of
graphs $mathcal{G}$ is in a set-of relationship with the class
$mathcal{C}$ of connected components, namely
$$deftextsc#1{dosc#1csod}
defdosc#1#2csod{{rm #1{small #2}}}
bbox[5px,border:2px solid #00A000]{
mathcal{G} = textsc{SET}(mathcal{C}).}$$
The class of graphs $mathcal{C}_k$ with $k$ connected components is
then given by
$$mathcal{C}_{k} = textsc{SET}_{=k}(mathcal{C}).$$
Translating to generating functions we thus have
$$G(z) = exp C(z)
quadtext{or}quad
C(z) = log G(z)$$
and
$$bbox[5px,border:2px solid #00A000]{
C_k(z) = frac{log^k G(z)}{k!}.}$$
Differentiating (here $kge 1$) we have
$$C_k(z)' = C_{k-1}(z) frac{G'(z)}{G(z)}
quadtext{or}quad
C_k(z)' G(z) = C_{k-1}(z) G'(z).$$
Writing $$C_k(z) = sum_{nge 0} C_{n,k} frac{z^n}{n!}$$
and extracting coefficients we have
$$[z^{n-1}] C_k(z)' G(z) = [z^{n-1}] C_{k-1}(z) G'(z)$$
which is
$$sum_{q=0}^{n-1} C_{q+1, k} frac{1}{q!}
2^{n-1-qchoose 2} frac{1}{(n-1-q)!}
= sum_{q=0}^{n-1} C_{q, k-1} frac{1}{q!}
2^{n-qchoose 2} frac{1}{(n-1-q)!}.$$
or
$$sum_{q=0}^{n-1} {n-1choose q} C_{q+1, k}
2^{n-1-qchoose 2}
= sum_{q=0}^{n-1} {n-1choose q} C_{q, k-1}
2^{n-qchoose 2}.$$
This yields the recurrence
$$bbox[5px,border:2px solid #00A000]{
C_{n, k} = sum_{q=0}^{n-1} {n-1choose q} C_{q, k-1}
2^{n-qchoose 2}
- sum_{q=0}^{n-2} {n-1choose q} C_{q+1, k}
2^{n-1-qchoose 2}.}$$
The base case is that when $k=0$ and $n=0$ we get the empty graph,
when $k=0$ or $n=0$ but not both we have zero. This yields
for one component the sequence
$$1, 1, 4, 38, 728, 26704, 1866256, 251548592,
\ 66296291072, 34496488594816, 35641657548953344,
\ 73354596206766622208, 301272202649664088951808, ldots $$
which points to OEIS A001187 where the
data are confirmed. Listing the $C_{n,k}$ in order with increasing $k$
for fixed $n$ and increasing $n$ (triangular array) we find
$$1, 1, 1, 4, 3, 1, 38, 19, 6, 1, 728, 230, 55, 10, 1, 26704,
\ 5098, 825, 125, 15, 1, 1866256, 207536, 20818, 2275, 245,
\ 21, 1, 251548592, 15891372, 925036, 64673, 5320, 434, 28, 1,
ldots $$
which points to OEIS A143543, where we get
confirmation once more. The reader who wants to experiment with these
exponential generating functions is invited to consult the following
Maple code.
CGF :=
proc(n, k)
option remember;
local G;
G := add(2^binomial(q,2)*z^q/q!, q=0..n);
n!*coeftayl(log(G)^k/k!, z=0, n);
end;
C :=
proc(n, k)
option remember;
if k = 0 and n = 0 then return 1 fi;
if k = 0 or n = 0 then return 0 fi;
add(binomial(n-1,q)*C(q,k-1)*2^binomial(n-q,2),
q=0..n-1)
- add(binomial(n-1,q)*C(q+1,k)*2^binomial(n-1-q,2),
q=0..n-2);
end;
OEIS := mx -> seq(seq(C(n,k), k=1..n), n=1..mx);
As a sanity check when we compute $sum_{k=1}^n C_{n,k}$ using the
values from the recurrence we really do obtain $2^{nchoose 2}.$
answered Feb 4 at 17:24
Marko RiedelMarko Riedel
41.2k340111
$endgroup$
$begingroup$
Great answer. Very instructive. (+1)
$endgroup$
– Markus Scheuer
Feb 4 at 18:31
add a comment |
$begingroup$
It's feasible to reduce the problem to finding an exponential generating function for the number of connected graphs.
Let $C(j,l,k)$ be the number of graphs on $j$ labeled vertices and $l$ edges with $k$ components. Use the convention that an empty graph has zero components, so $C(0,0,0)=1$ and $C(0,l,k)=0$ for all other $l,k$.
Consider the component containing vertex $1$ in a graph of $n$ vertices, $m$ edges, and $k$ components. If that component has $j$ vertices and $l$ edges, there are $n-j$ vertices and $m-l$ edges left for the remaining $k-1$ components, so
begin{align*}C(n,m,k) &= sum_{1in Ssubset [n]}sum_l C(|S|,l,1)cdot C(n-|S|,m-l,k-1)\
&= sum_jsum_lbinom{n}{j}C(j,l,1)cdot C(n-j,m-l,k-1)end{align*}
Our choice to put $1$ in the first component means $jge 1$ - but since $C(0,l,1)=0$, we can add $j=0$ back in and just sum over all $j$. Back to the issue at hand - yeah, that looks like an exponential-type convolution. Define $B(n,m,k)=frac1{n!}C(n,m,k)$, and it becomes
$$B(n,m,k)=sum_jsum_l B(j,l,1)cdot B(n-j,m-l,k-1)$$
Now define $f_k(x,y)=sum_nsum_mB(n,m,k)x^ny^m$. Our relation for the $B$ becomes
$$f_k(x,y)=f_1(x,y)cdot f_{k-1}(x,y)$$
so $f_k(x,y)=left(f_1(x,y)right)^k$. Whatever the exponential generating function for connected graphs is, we raise it to the $k$th power to get the exponential generating function for $k$-component graphs.
OK, one more thing. Since every graph has some number of connected components, we can sum over $k$:
$$frac1{1-f(x,y)} = sum_k f^k(x,y) = sum_{m,n}frac1{n!}binom{binom{n}{2}}{m}x^ny^m = sum_nfrac{x^n}{n!}(1+y)^{n(n-1)/2}$$
where $f$ is the EGF for the number of connected graphs and the right hand side is the EGF for the number of total graphs. I doubt the latter has an elementary closed form, so that's as far as it goes. We could solve for $f$, writing the other side as a series of powers of that generating function (minus its constant term $1$), but that's messier without any clear benefit.
answered Jan 31 at 9:32
jmerryjmerry
17k11633
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3094635%2fgenerating-function-for-the-number-of-graphs-with-k-connected-components%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
OP is asking for credible and/or official sources. We cite the Labeled Counting Lemma stated in Graphical Enumeration by F. Harary and E.M. Palmer. This lemma is important since it clarifies the usage of exponential generating functions and the authors just use connected, labeled graphs with $n$ components as demonstration of this lemma.
A theorem in section 1.2 Connected graphs states: The number $C_k$ of connected, labeled graphs with $k$ nodes is
begin{align*}
color{blue}{C_k=2^{binom{k}{2}}-frac{1}{k}sum_{j=1}^{k-1}binom{k}{j}j2^{binom{k-j}{2}}C_j}tag{1}
end{align*}
Let $C(x)$ denote the exponential generating function for the connected, labeled graphs. We find the sequence $(C_k)_{kgeq 0}$ in OEIS as A001187 with generating function
begin{align*}
sum_{k=0}^infty C_kfrac{x^k}{k!}&=1+logleft(sum_{j=0}^infty 2^{binom{j}{2}}frac{x^j}{j!}right)\
&=1+x + frac{x^2}{2!} + 4frac{x^3}{3!} + 38frac{x^4}{4!} + 728frac{x^5}{5!}\
&qquad + 26,704frac{x^6}{6!} + 1,866,256frac{x^7}{7!} + cdots
end{align*}
We start with a motivation for exponential generating functions followed by the labeled counting lemma.
Harary, Palmer: section 1.2
It is important to have at hand the concept of the exponential generating function and some of its associated properties. We shall therefore introduce these functions now ...
For each $k=1,2,3,ldots$, let $a_k$ be the number of ways of labeling all graphs of order $k$ which have some property $P(a)$. Then the formal power series
begin{align*}
a(x)=sum_{k=1}^infty a_kx^k/k!
end{align*}
is called the exponential generating function for the class of graphs at hand. Suppose also that
begin{align*}
b(x)=sum_{k=1}^infty b_kx^k/k!
end{align*}
is another exponential generating function for a class of graphs with property $P(b)$.
The next lemma provides a useful interpretation of the coefficients of the product $a(x)b(x)$ of these two generating functions.
Labeled Counting Lemma: The coefficient of $x^k/k!$ in $a(x)b(x)$ is the number of ordered pairs $(G_1,G_2)$ of two disjoint graphs, where $G_1$ has property $P(a)$, $G_2$ has property $P(b)$, $k$ is the number of points in $G_1cup G_2$ and the labels $1$ through $k$ have been distributed over $G_1cup G_2$.
- To illustrate, let $C(x)$ be the exponential generating functions for labeled, connected graphs,
begin{align*}
C(x)=sum_{k=1}^infty C_k x^k/k!
end{align*}
- Then $C(x)C(x)$ is the generating function for ordered pairs of labeled, connected graphs. On dividing this series by $2$, we have the generating function for labeled graphs which have exactly two components. Similarly $C^n(x)/n!$ has as the coefficient of $x^k/k!$, the number of labeled graphs of order $k$ with exactly $n$ components. If we let $G(x)$ be the exponential generating function for labeled graphs, we then have
begin{align*}
color{blue}{G(x)=sum_{n=1}^infty C^n(x)/n!}tag{2}
end{align*}
The last paragraph together with (2) reveals the connection between labeled, connected graphs and labeled graphs consisting of $n$ components. The authors close this section by presenting the functional equation connecting $G(x)$ with $C(x)$.
Thus we have the following exponential relationship for $G(x)$ and $C(x)$ found by R.J. Riddel [Contributions to the theory of condensation, Dissertation, 1951].
Theorem: The exponential generating function $G(x)$ and $C(x)$ for labeled graphs and labeled connected graphs come to terms in the following relation
begin{align*}
1+G(x)=e^{C(x)}
end{align*}
answered Feb 3 at 21:03
Markus ScheuerMarkus Scheuer
63.8k460152
$endgroup$
$begingroup$
Upvoted. (+1). These are useful references to a classic text.
$endgroup$
– Marko Riedel
Feb 4 at 17:25
add a comment |
$begingroup$
OP is asking for credible and/or official sources. We cite the Labeled Counting Lemma stated in Graphical Enumeration by F. Harary and E.M. Palmer. This lemma is important since it clarifies the usage of exponential generating functions and the authors just use connected, labeled graphs with $n$ components as demonstration of this lemma.
A theorem in section 1.2 Connected graphs states: The number $C_k$ of connected, labeled graphs with $k$ nodes is
begin{align*}
color{blue}{C_k=2^{binom{k}{2}}-frac{1}{k}sum_{j=1}^{k-1}binom{k}{j}j2^{binom{k-j}{2}}C_j}tag{1}
end{align*}
Let $C(x)$ denote the exponential generating function for the connected, labeled graphs. We find the sequence $(C_k)_{kgeq 0}$ in OEIS as A001187 with generating function
begin{align*}
sum_{k=0}^infty C_kfrac{x^k}{k!}&=1+logleft(sum_{j=0}^infty 2^{binom{j}{2}}frac{x^j}{j!}right)\
&=1+x + frac{x^2}{2!} + 4frac{x^3}{3!} + 38frac{x^4}{4!} + 728frac{x^5}{5!}\
&qquad + 26,704frac{x^6}{6!} + 1,866,256frac{x^7}{7!} + cdots
end{align*}
We start with a motivation for exponential generating functions followed by the labeled counting lemma.
Harary, Palmer: section 1.2
It is important to have at hand the concept of the exponential generating function and some of its associated properties. We shall therefore introduce these functions now ...
For each $k=1,2,3,ldots$, let $a_k$ be the number of ways of labeling all graphs of order $k$ which have some property $P(a)$. Then the formal power series
begin{align*}
a(x)=sum_{k=1}^infty a_kx^k/k!
end{align*}
is called the exponential generating function for the class of graphs at hand. Suppose also that
begin{align*}
b(x)=sum_{k=1}^infty b_kx^k/k!
end{align*}
is another exponential generating function for a class of graphs with property $P(b)$.
The next lemma provides a useful interpretation of the coefficients of the product $a(x)b(x)$ of these two generating functions.
Labeled Counting Lemma: The coefficient of $x^k/k!$ in $a(x)b(x)$ is the number of ordered pairs $(G_1,G_2)$ of two disjoint graphs, where $G_1$ has property $P(a)$, $G_2$ has property $P(b)$, $k$ is the number of points in $G_1cup G_2$ and the labels $1$ through $k$ have been distributed over $G_1cup G_2$.
- To illustrate, let $C(x)$ be the exponential generating functions for labeled, connected graphs,
begin{align*}
C(x)=sum_{k=1}^infty C_k x^k/k!
end{align*}
- Then $C(x)C(x)$ is the generating function for ordered pairs of labeled, connected graphs. On dividing this series by $2$, we have the generating function for labeled graphs which have exactly two components. Similarly $C^n(x)/n!$ has as the coefficient of $x^k/k!$, the number of labeled graphs of order $k$ with exactly $n$ components. If we let $G(x)$ be the exponential generating function for labeled graphs, we then have
begin{align*}
color{blue}{G(x)=sum_{n=1}^infty C^n(x)/n!}tag{2}
end{align*}
The last paragraph together with (2) reveals the connection between labeled, connected graphs and labeled graphs consisting of $n$ components. The authors close this section by presenting the functional equation connecting $G(x)$ with $C(x)$.
Thus we have the following exponential relationship for $G(x)$ and $C(x)$ found by R.J. Riddel [Contributions to the theory of condensation, Dissertation, 1951].
Theorem: The exponential generating function $G(x)$ and $C(x)$ for labeled graphs and labeled connected graphs come to terms in the following relation
begin{align*}
1+G(x)=e^{C(x)}
end{align*}
answered Feb 3 at 21:03
Markus ScheuerMarkus Scheuer
63.8k460152
$endgroup$
$begingroup$
Upvoted. (+1). These are useful references to a classic text.
$endgroup$
– Marko Riedel
Feb 4 at 17:25
add a comment |
$begingroup$
OP is asking for credible and/or official sources. We cite the Labeled Counting Lemma stated in Graphical Enumeration by F. Harary and E.M. Palmer. This lemma is important since it clarifies the usage of exponential generating functions and the authors just use connected, labeled graphs with $n$ components as demonstration of this lemma.
A theorem in section 1.2 Connected graphs states: The number $C_k$ of connected, labeled graphs with $k$ nodes is
begin{align*}
color{blue}{C_k=2^{binom{k}{2}}-frac{1}{k}sum_{j=1}^{k-1}binom{k}{j}j2^{binom{k-j}{2}}C_j}tag{1}
end{align*}
Let $C(x)$ denote the exponential generating function for the connected, labeled graphs. We find the sequence $(C_k)_{kgeq 0}$ in OEIS as A001187 with generating function
begin{align*}
sum_{k=0}^infty C_kfrac{x^k}{k!}&=1+logleft(sum_{j=0}^infty 2^{binom{j}{2}}frac{x^j}{j!}right)\
&=1+x + frac{x^2}{2!} + 4frac{x^3}{3!} + 38frac{x^4}{4!} + 728frac{x^5}{5!}\
&qquad + 26,704frac{x^6}{6!} + 1,866,256frac{x^7}{7!} + cdots
end{align*}
We start with a motivation for exponential generating functions followed by the labeled counting lemma.
Harary, Palmer: section 1.2
It is important to have at hand the concept of the exponential generating function and some of its associated properties. We shall therefore introduce these functions now ...
For each $k=1,2,3,ldots$, let $a_k$ be the number of ways of labeling all graphs of order $k$ which have some property $P(a)$. Then the formal power series
begin{align*}
a(x)=sum_{k=1}^infty a_kx^k/k!
end{align*}
is called the exponential generating function for the class of graphs at hand. Suppose also that
begin{align*}
b(x)=sum_{k=1}^infty b_kx^k/k!
end{align*}
is another exponential generating function for a class of graphs with property $P(b)$.
The next lemma provides a useful interpretation of the coefficients of the product $a(x)b(x)$ of these two generating functions.
Labeled Counting Lemma: The coefficient of $x^k/k!$ in $a(x)b(x)$ is the number of ordered pairs $(G_1,G_2)$ of two disjoint graphs, where $G_1$ has property $P(a)$, $G_2$ has property $P(b)$, $k$ is the number of points in $G_1cup G_2$ and the labels $1$ through $k$ have been distributed over $G_1cup G_2$.
- To illustrate, let $C(x)$ be the exponential generating functions for labeled, connected graphs,
begin{align*}
C(x)=sum_{k=1}^infty C_k x^k/k!
end{align*}
- Then $C(x)C(x)$ is the generating function for ordered pairs of labeled, connected graphs. On dividing this series by $2$, we have the generating function for labeled graphs which have exactly two components. Similarly $C^n(x)/n!$ has as the coefficient of $x^k/k!$, the number of labeled graphs of order $k$ with exactly $n$ components. If we let $G(x)$ be the exponential generating function for labeled graphs, we then have
begin{align*}
color{blue}{G(x)=sum_{n=1}^infty C^n(x)/n!}tag{2}
end{align*}
The last paragraph together with (2) reveals the connection between labeled, connected graphs and labeled graphs consisting of $n$ components. The authors close this section by presenting the functional equation connecting $G(x)$ with $C(x)$.
Thus we have the following exponential relationship for $G(x)$ and $C(x)$ found by R.J. Riddel [Contributions to the theory of condensation, Dissertation, 1951].
Theorem: The exponential generating function $G(x)$ and $C(x)$ for labeled graphs and labeled connected graphs come to terms in the following relation
begin{align*}
1+G(x)=e^{C(x)}
end{align*}
answered Feb 3 at 21:03
Markus ScheuerMarkus Scheuer
63.8k460152
$endgroup$
OP is asking for credible and/or official sources. We cite the Labeled Counting Lemma stated in Graphical Enumeration by F. Harary and E.M. Palmer. This lemma is important since it clarifies the usage of exponential generating functions and the authors just use connected, labeled graphs with $n$ components as demonstration of this lemma.
A theorem in section 1.2 Connected graphs states: The number $C_k$ of connected, labeled graphs with $k$ nodes is
begin{align*}
color{blue}{C_k=2^{binom{k}{2}}-frac{1}{k}sum_{j=1}^{k-1}binom{k}{j}j2^{binom{k-j}{2}}C_j}tag{1}
end{align*}
Let $C(x)$ denote the exponential generating function for the connected, labeled graphs. We find the sequence $(C_k)_{kgeq 0}$ in OEIS as A001187 with generating function
begin{align*}
sum_{k=0}^infty C_kfrac{x^k}{k!}&=1+logleft(sum_{j=0}^infty 2^{binom{j}{2}}frac{x^j}{j!}right)\
&=1+x + frac{x^2}{2!} + 4frac{x^3}{3!} + 38frac{x^4}{4!} + 728frac{x^5}{5!}\
&qquad + 26,704frac{x^6}{6!} + 1,866,256frac{x^7}{7!} + cdots
end{align*}
We start with a motivation for exponential generating functions followed by the labeled counting lemma.
Harary, Palmer: section 1.2
It is important to have at hand the concept of the exponential generating function and some of its associated properties. We shall therefore introduce these functions now ...
For each $k=1,2,3,ldots$, let $a_k$ be the number of ways of labeling all graphs of order $k$ which have some property $P(a)$. Then the formal power series
begin{align*}
a(x)=sum_{k=1}^infty a_kx^k/k!
end{align*}
is called the exponential generating function for the class of graphs at hand. Suppose also that
begin{align*}
b(x)=sum_{k=1}^infty b_kx^k/k!
end{align*}
is another exponential generating function for a class of graphs with property $P(b)$.
The next lemma provides a useful interpretation of the coefficients of the product $a(x)b(x)$ of these two generating functions.
Labeled Counting Lemma: The coefficient of $x^k/k!$ in $a(x)b(x)$ is the number of ordered pairs $(G_1,G_2)$ of two disjoint graphs, where $G_1$ has property $P(a)$, $G_2$ has property $P(b)$, $k$ is the number of points in $G_1cup G_2$ and the labels $1$ through $k$ have been distributed over $G_1cup G_2$.
- To illustrate, let $C(x)$ be the exponential generating functions for labeled, connected graphs,
begin{align*}
C(x)=sum_{k=1}^infty C_k x^k/k!
end{align*}
- Then $C(x)C(x)$ is the generating function for ordered pairs of labeled, connected graphs. On dividing this series by $2$, we have the generating function for labeled graphs which have exactly two components. Similarly $C^n(x)/n!$ has as the coefficient of $x^k/k!$, the number of labeled graphs of order $k$ with exactly $n$ components. If we let $G(x)$ be the exponential generating function for labeled graphs, we then have
begin{align*}
color{blue}{G(x)=sum_{n=1}^infty C^n(x)/n!}tag{2}
end{align*}
The last paragraph together with (2) reveals the connection between labeled, connected graphs and labeled graphs consisting of $n$ components. The authors close this section by presenting the functional equation connecting $G(x)$ with $C(x)$.
Thus we have the following exponential relationship for $G(x)$ and $C(x)$ found by R.J. Riddel [Contributions to the theory of condensation, Dissertation, 1951].
Theorem: The exponential generating function $G(x)$ and $C(x)$ for labeled graphs and labeled connected graphs come to terms in the following relation
begin{align*}
1+G(x)=e^{C(x)}
end{align*}
answered Feb 3 at 21:03
Markus ScheuerMarkus Scheuer
63.8k460152
answered Feb 3 at 21:03
Markus ScheuerMarkus Scheuer
63.8k460152
answered Feb 3 at 21:03
Markus ScheuerMarkus Scheuer
63.8k460152
answered Feb 3 at 21:03
Markus ScheuerMarkus Scheuer
63.8k460152
63.8k460152
$begingroup$
Upvoted. (+1). These are useful references to a classic text.
$endgroup$
– Marko Riedel
Feb 4 at 17:25
add a comment |
$begingroup$
Upvoted. (+1). These are useful references to a classic text.
$endgroup$
– Marko Riedel
Feb 4 at 17:25
$begingroup$
Upvoted. (+1). These are useful references to a classic text.
$endgroup$
– Marko Riedel
Feb 4 at 17:25
$begingroup$
Upvoted. (+1). These are useful references to a classic text.
$endgroup$
– Marko Riedel
Feb 4 at 17:25
add a comment |
$begingroup$
We compute a recurrence for the number of labeled graphs with $k$
components. With $G(z)$ the EGF of labeled graphs we have
$$G(z) = sum_{nge 0} 2^{nchoose 2} frac{z^n}{n!}.$$
Here we have included the empty graph on zero nodes. Now the class of
graphs $mathcal{G}$ is in a set-of relationship with the class
$mathcal{C}$ of connected components, namely
$$deftextsc#1{dosc#1csod}
defdosc#1#2csod{{rm #1{small #2}}}
bbox[5px,border:2px solid #00A000]{
mathcal{G} = textsc{SET}(mathcal{C}).}$$
The class of graphs $mathcal{C}_k$ with $k$ connected components is
then given by
$$mathcal{C}_{k} = textsc{SET}_{=k}(mathcal{C}).$$
Translating to generating functions we thus have
$$G(z) = exp C(z)
quadtext{or}quad
C(z) = log G(z)$$
and
$$bbox[5px,border:2px solid #00A000]{
C_k(z) = frac{log^k G(z)}{k!}.}$$
Differentiating (here $kge 1$) we have
$$C_k(z)' = C_{k-1}(z) frac{G'(z)}{G(z)}
quadtext{or}quad
C_k(z)' G(z) = C_{k-1}(z) G'(z).$$
Writing $$C_k(z) = sum_{nge 0} C_{n,k} frac{z^n}{n!}$$
and extracting coefficients we have
$$[z^{n-1}] C_k(z)' G(z) = [z^{n-1}] C_{k-1}(z) G'(z)$$
which is
$$sum_{q=0}^{n-1} C_{q+1, k} frac{1}{q!}
2^{n-1-qchoose 2} frac{1}{(n-1-q)!}
= sum_{q=0}^{n-1} C_{q, k-1} frac{1}{q!}
2^{n-qchoose 2} frac{1}{(n-1-q)!}.$$
or
$$sum_{q=0}^{n-1} {n-1choose q} C_{q+1, k}
2^{n-1-qchoose 2}
= sum_{q=0}^{n-1} {n-1choose q} C_{q, k-1}
2^{n-qchoose 2}.$$
This yields the recurrence
$$bbox[5px,border:2px solid #00A000]{
C_{n, k} = sum_{q=0}^{n-1} {n-1choose q} C_{q, k-1}
2^{n-qchoose 2}
- sum_{q=0}^{n-2} {n-1choose q} C_{q+1, k}
2^{n-1-qchoose 2}.}$$
The base case is that when $k=0$ and $n=0$ we get the empty graph,
when $k=0$ or $n=0$ but not both we have zero. This yields
for one component the sequence
$$1, 1, 4, 38, 728, 26704, 1866256, 251548592,
\ 66296291072, 34496488594816, 35641657548953344,
\ 73354596206766622208, 301272202649664088951808, ldots $$
which points to OEIS A001187 where the
data are confirmed. Listing the $C_{n,k}$ in order with increasing $k$
for fixed $n$ and increasing $n$ (triangular array) we find
$$1, 1, 1, 4, 3, 1, 38, 19, 6, 1, 728, 230, 55, 10, 1, 26704,
\ 5098, 825, 125, 15, 1, 1866256, 207536, 20818, 2275, 245,
\ 21, 1, 251548592, 15891372, 925036, 64673, 5320, 434, 28, 1,
ldots $$
which points to OEIS A143543, where we get
confirmation once more. The reader who wants to experiment with these
exponential generating functions is invited to consult the following
Maple code.
CGF :=
proc(n, k)
option remember;
local G;
G := add(2^binomial(q,2)*z^q/q!, q=0..n);
n!*coeftayl(log(G)^k/k!, z=0, n);
end;
C :=
proc(n, k)
option remember;
if k = 0 and n = 0 then return 1 fi;
if k = 0 or n = 0 then return 0 fi;
add(binomial(n-1,q)*C(q,k-1)*2^binomial(n-q,2),
q=0..n-1)
- add(binomial(n-1,q)*C(q+1,k)*2^binomial(n-1-q,2),
q=0..n-2);
end;
OEIS := mx -> seq(seq(C(n,k), k=1..n), n=1..mx);
As a sanity check when we compute $sum_{k=1}^n C_{n,k}$ using the
values from the recurrence we really do obtain $2^{nchoose 2}.$
answered Feb 4 at 17:24
Marko RiedelMarko Riedel
41.2k340111
$endgroup$
$begingroup$
Great answer. Very instructive. (+1)
$endgroup$
– Markus Scheuer
Feb 4 at 18:31
add a comment |
$begingroup$
We compute a recurrence for the number of labeled graphs with $k$
components. With $G(z)$ the EGF of labeled graphs we have
$$G(z) = sum_{nge 0} 2^{nchoose 2} frac{z^n}{n!}.$$
Here we have included the empty graph on zero nodes. Now the class of
graphs $mathcal{G}$ is in a set-of relationship with the class
$mathcal{C}$ of connected components, namely
$$deftextsc#1{dosc#1csod}
defdosc#1#2csod{{rm #1{small #2}}}
bbox[5px,border:2px solid #00A000]{
mathcal{G} = textsc{SET}(mathcal{C}).}$$
The class of graphs $mathcal{C}_k$ with $k$ connected components is
then given by
$$mathcal{C}_{k} = textsc{SET}_{=k}(mathcal{C}).$$
Translating to generating functions we thus have
$$G(z) = exp C(z)
quadtext{or}quad
C(z) = log G(z)$$
and
$$bbox[5px,border:2px solid #00A000]{
C_k(z) = frac{log^k G(z)}{k!}.}$$
Differentiating (here $kge 1$) we have
$$C_k(z)' = C_{k-1}(z) frac{G'(z)}{G(z)}
quadtext{or}quad
C_k(z)' G(z) = C_{k-1}(z) G'(z).$$
Writing $$C_k(z) = sum_{nge 0} C_{n,k} frac{z^n}{n!}$$
and extracting coefficients we have
$$[z^{n-1}] C_k(z)' G(z) = [z^{n-1}] C_{k-1}(z) G'(z)$$
which is
$$sum_{q=0}^{n-1} C_{q+1, k} frac{1}{q!}
2^{n-1-qchoose 2} frac{1}{(n-1-q)!}
= sum_{q=0}^{n-1} C_{q, k-1} frac{1}{q!}
2^{n-qchoose 2} frac{1}{(n-1-q)!}.$$
or
$$sum_{q=0}^{n-1} {n-1choose q} C_{q+1, k}
2^{n-1-qchoose 2}
= sum_{q=0}^{n-1} {n-1choose q} C_{q, k-1}
2^{n-qchoose 2}.$$
This yields the recurrence
$$bbox[5px,border:2px solid #00A000]{
C_{n, k} = sum_{q=0}^{n-1} {n-1choose q} C_{q, k-1}
2^{n-qchoose 2}
- sum_{q=0}^{n-2} {n-1choose q} C_{q+1, k}
2^{n-1-qchoose 2}.}$$
The base case is that when $k=0$ and $n=0$ we get the empty graph,
when $k=0$ or $n=0$ but not both we have zero. This yields
for one component the sequence
$$1, 1, 4, 38, 728, 26704, 1866256, 251548592,
\ 66296291072, 34496488594816, 35641657548953344,
\ 73354596206766622208, 301272202649664088951808, ldots $$
which points to OEIS A001187 where the
data are confirmed. Listing the $C_{n,k}$ in order with increasing $k$
for fixed $n$ and increasing $n$ (triangular array) we find
$$1, 1, 1, 4, 3, 1, 38, 19, 6, 1, 728, 230, 55, 10, 1, 26704,
\ 5098, 825, 125, 15, 1, 1866256, 207536, 20818, 2275, 245,
\ 21, 1, 251548592, 15891372, 925036, 64673, 5320, 434, 28, 1,
ldots $$
which points to OEIS A143543, where we get
confirmation once more. The reader who wants to experiment with these
exponential generating functions is invited to consult the following
Maple code.
CGF :=
proc(n, k)
option remember;
local G;
G := add(2^binomial(q,2)*z^q/q!, q=0..n);
n!*coeftayl(log(G)^k/k!, z=0, n);
end;
C :=
proc(n, k)
option remember;
if k = 0 and n = 0 then return 1 fi;
if k = 0 or n = 0 then return 0 fi;
add(binomial(n-1,q)*C(q,k-1)*2^binomial(n-q,2),
q=0..n-1)
- add(binomial(n-1,q)*C(q+1,k)*2^binomial(n-1-q,2),
q=0..n-2);
end;
OEIS := mx -> seq(seq(C(n,k), k=1..n), n=1..mx);
As a sanity check when we compute $sum_{k=1}^n C_{n,k}$ using the
values from the recurrence we really do obtain $2^{nchoose 2}.$
answered Feb 4 at 17:24
Marko RiedelMarko Riedel
41.2k340111
$endgroup$
$begingroup$
Great answer. Very instructive. (+1)
$endgroup$
– Markus Scheuer
Feb 4 at 18:31
add a comment |
$begingroup$
We compute a recurrence for the number of labeled graphs with $k$
components. With $G(z)$ the EGF of labeled graphs we have
$$G(z) = sum_{nge 0} 2^{nchoose 2} frac{z^n}{n!}.$$
Here we have included the empty graph on zero nodes. Now the class of
graphs $mathcal{G}$ is in a set-of relationship with the class
$mathcal{C}$ of connected components, namely
$$deftextsc#1{dosc#1csod}
defdosc#1#2csod{{rm #1{small #2}}}
bbox[5px,border:2px solid #00A000]{
mathcal{G} = textsc{SET}(mathcal{C}).}$$
The class of graphs $mathcal{C}_k$ with $k$ connected components is
then given by
$$mathcal{C}_{k} = textsc{SET}_{=k}(mathcal{C}).$$
Translating to generating functions we thus have
$$G(z) = exp C(z)
quadtext{or}quad
C(z) = log G(z)$$
and
$$bbox[5px,border:2px solid #00A000]{
C_k(z) = frac{log^k G(z)}{k!}.}$$
Differentiating (here $kge 1$) we have
$$C_k(z)' = C_{k-1}(z) frac{G'(z)}{G(z)}
quadtext{or}quad
C_k(z)' G(z) = C_{k-1}(z) G'(z).$$
Writing $$C_k(z) = sum_{nge 0} C_{n,k} frac{z^n}{n!}$$
and extracting coefficients we have
$$[z^{n-1}] C_k(z)' G(z) = [z^{n-1}] C_{k-1}(z) G'(z)$$
which is
$$sum_{q=0}^{n-1} C_{q+1, k} frac{1}{q!}
2^{n-1-qchoose 2} frac{1}{(n-1-q)!}
= sum_{q=0}^{n-1} C_{q, k-1} frac{1}{q!}
2^{n-qchoose 2} frac{1}{(n-1-q)!}.$$
or
$$sum_{q=0}^{n-1} {n-1choose q} C_{q+1, k}
2^{n-1-qchoose 2}
= sum_{q=0}^{n-1} {n-1choose q} C_{q, k-1}
2^{n-qchoose 2}.$$
This yields the recurrence
$$bbox[5px,border:2px solid #00A000]{
C_{n, k} = sum_{q=0}^{n-1} {n-1choose q} C_{q, k-1}
2^{n-qchoose 2}
- sum_{q=0}^{n-2} {n-1choose q} C_{q+1, k}
2^{n-1-qchoose 2}.}$$
The base case is that when $k=0$ and $n=0$ we get the empty graph,
when $k=0$ or $n=0$ but not both we have zero. This yields
for one component the sequence
$$1, 1, 4, 38, 728, 26704, 1866256, 251548592,
\ 66296291072, 34496488594816, 35641657548953344,
\ 73354596206766622208, 301272202649664088951808, ldots $$
which points to OEIS A001187 where the
data are confirmed. Listing the $C_{n,k}$ in order with increasing $k$
for fixed $n$ and increasing $n$ (triangular array) we find
$$1, 1, 1, 4, 3, 1, 38, 19, 6, 1, 728, 230, 55, 10, 1, 26704,
\ 5098, 825, 125, 15, 1, 1866256, 207536, 20818, 2275, 245,
\ 21, 1, 251548592, 15891372, 925036, 64673, 5320, 434, 28, 1,
ldots $$
which points to OEIS A143543, where we get
confirmation once more. The reader who wants to experiment with these
exponential generating functions is invited to consult the following
Maple code.
CGF :=
proc(n, k)
option remember;
local G;
G := add(2^binomial(q,2)*z^q/q!, q=0..n);
n!*coeftayl(log(G)^k/k!, z=0, n);
end;
C :=
proc(n, k)
option remember;
if k = 0 and n = 0 then return 1 fi;
if k = 0 or n = 0 then return 0 fi;
add(binomial(n-1,q)*C(q,k-1)*2^binomial(n-q,2),
q=0..n-1)
- add(binomial(n-1,q)*C(q+1,k)*2^binomial(n-1-q,2),
q=0..n-2);
end;
OEIS := mx -> seq(seq(C(n,k), k=1..n), n=1..mx);
As a sanity check when we compute $sum_{k=1}^n C_{n,k}$ using the
values from the recurrence we really do obtain $2^{nchoose 2}.$
answered Feb 4 at 17:24
Marko RiedelMarko Riedel
41.2k340111
$endgroup$
We compute a recurrence for the number of labeled graphs with $k$
components. With $G(z)$ the EGF of labeled graphs we have
$$G(z) = sum_{nge 0} 2^{nchoose 2} frac{z^n}{n!}.$$
Here we have included the empty graph on zero nodes. Now the class of
graphs $mathcal{G}$ is in a set-of relationship with the class
$mathcal{C}$ of connected components, namely
$$deftextsc#1{dosc#1csod}
defdosc#1#2csod{{rm #1{small #2}}}
bbox[5px,border:2px solid #00A000]{
mathcal{G} = textsc{SET}(mathcal{C}).}$$
The class of graphs $mathcal{C}_k$ with $k$ connected components is
then given by
$$mathcal{C}_{k} = textsc{SET}_{=k}(mathcal{C}).$$
Translating to generating functions we thus have
$$G(z) = exp C(z)
quadtext{or}quad
C(z) = log G(z)$$
and
$$bbox[5px,border:2px solid #00A000]{
C_k(z) = frac{log^k G(z)}{k!}.}$$
Differentiating (here $kge 1$) we have
$$C_k(z)' = C_{k-1}(z) frac{G'(z)}{G(z)}
quadtext{or}quad
C_k(z)' G(z) = C_{k-1}(z) G'(z).$$
Writing $$C_k(z) = sum_{nge 0} C_{n,k} frac{z^n}{n!}$$
and extracting coefficients we have
$$[z^{n-1}] C_k(z)' G(z) = [z^{n-1}] C_{k-1}(z) G'(z)$$
which is
$$sum_{q=0}^{n-1} C_{q+1, k} frac{1}{q!}
2^{n-1-qchoose 2} frac{1}{(n-1-q)!}
= sum_{q=0}^{n-1} C_{q, k-1} frac{1}{q!}
2^{n-qchoose 2} frac{1}{(n-1-q)!}.$$
or
$$sum_{q=0}^{n-1} {n-1choose q} C_{q+1, k}
2^{n-1-qchoose 2}
= sum_{q=0}^{n-1} {n-1choose q} C_{q, k-1}
2^{n-qchoose 2}.$$
This yields the recurrence
$$bbox[5px,border:2px solid #00A000]{
C_{n, k} = sum_{q=0}^{n-1} {n-1choose q} C_{q, k-1}
2^{n-qchoose 2}
- sum_{q=0}^{n-2} {n-1choose q} C_{q+1, k}
2^{n-1-qchoose 2}.}$$
The base case is that when $k=0$ and $n=0$ we get the empty graph,
when $k=0$ or $n=0$ but not both we have zero. This yields
for one component the sequence
$$1, 1, 4, 38, 728, 26704, 1866256, 251548592,
\ 66296291072, 34496488594816, 35641657548953344,
\ 73354596206766622208, 301272202649664088951808, ldots $$
which points to OEIS A001187 where the
data are confirmed. Listing the $C_{n,k}$ in order with increasing $k$
for fixed $n$ and increasing $n$ (triangular array) we find
$$1, 1, 1, 4, 3, 1, 38, 19, 6, 1, 728, 230, 55, 10, 1, 26704,
\ 5098, 825, 125, 15, 1, 1866256, 207536, 20818, 2275, 245,
\ 21, 1, 251548592, 15891372, 925036, 64673, 5320, 434, 28, 1,
ldots $$
which points to OEIS A143543, where we get
confirmation once more. The reader who wants to experiment with these
exponential generating functions is invited to consult the following
Maple code.
CGF :=
proc(n, k)
option remember;
local G;
G := add(2^binomial(q,2)*z^q/q!, q=0..n);
n!*coeftayl(log(G)^k/k!, z=0, n);
end;
C :=
proc(n, k)
option remember;
if k = 0 and n = 0 then return 1 fi;
if k = 0 or n = 0 then return 0 fi;
add(binomial(n-1,q)*C(q,k-1)*2^binomial(n-q,2),
q=0..n-1)
- add(binomial(n-1,q)*C(q+1,k)*2^binomial(n-1-q,2),
q=0..n-2);
end;
OEIS := mx -> seq(seq(C(n,k), k=1..n), n=1..mx);
As a sanity check when we compute $sum_{k=1}^n C_{n,k}$ using the
values from the recurrence we really do obtain $2^{nchoose 2}.$
answered Feb 4 at 17:24
Marko RiedelMarko Riedel
41.2k340111
edited Feb 4 at 18:08
answered Feb 4 at 17:24
Marko RiedelMarko Riedel
41.2k340111
answered Feb 4 at 17:24
Marko RiedelMarko Riedel
41.2k340111
answered Feb 4 at 17:24
Marko RiedelMarko Riedel
41.2k340111
41.2k340111
$begingroup$
Great answer. Very instructive. (+1)
$endgroup$
– Markus Scheuer
Feb 4 at 18:31
add a comment |
$begingroup$
Great answer. Very instructive. (+1)
$endgroup$
– Markus Scheuer
Feb 4 at 18:31
$begingroup$
Great answer. Very instructive. (+1)
$endgroup$
– Markus Scheuer
Feb 4 at 18:31
$begingroup$
Great answer. Very instructive. (+1)
$endgroup$
– Markus Scheuer
Feb 4 at 18:31
add a comment |
$begingroup$
It's feasible to reduce the problem to finding an exponential generating function for the number of connected graphs.
Let $C(j,l,k)$ be the number of graphs on $j$ labeled vertices and $l$ edges with $k$ components. Use the convention that an empty graph has zero components, so $C(0,0,0)=1$ and $C(0,l,k)=0$ for all other $l,k$.
Consider the component containing vertex $1$ in a graph of $n$ vertices, $m$ edges, and $k$ components. If that component has $j$ vertices and $l$ edges, there are $n-j$ vertices and $m-l$ edges left for the remaining $k-1$ components, so
begin{align*}C(n,m,k) &= sum_{1in Ssubset [n]}sum_l C(|S|,l,1)cdot C(n-|S|,m-l,k-1)\
&= sum_jsum_lbinom{n}{j}C(j,l,1)cdot C(n-j,m-l,k-1)end{align*}
Our choice to put $1$ in the first component means $jge 1$ - but since $C(0,l,1)=0$, we can add $j=0$ back in and just sum over all $j$. Back to the issue at hand - yeah, that looks like an exponential-type convolution. Define $B(n,m,k)=frac1{n!}C(n,m,k)$, and it becomes
$$B(n,m,k)=sum_jsum_l B(j,l,1)cdot B(n-j,m-l,k-1)$$
Now define $f_k(x,y)=sum_nsum_mB(n,m,k)x^ny^m$. Our relation for the $B$ becomes
$$f_k(x,y)=f_1(x,y)cdot f_{k-1}(x,y)$$
so $f_k(x,y)=left(f_1(x,y)right)^k$. Whatever the exponential generating function for connected graphs is, we raise it to the $k$th power to get the exponential generating function for $k$-component graphs.
OK, one more thing. Since every graph has some number of connected components, we can sum over $k$:
$$frac1{1-f(x,y)} = sum_k f^k(x,y) = sum_{m,n}frac1{n!}binom{binom{n}{2}}{m}x^ny^m = sum_nfrac{x^n}{n!}(1+y)^{n(n-1)/2}$$
where $f$ is the EGF for the number of connected graphs and the right hand side is the EGF for the number of total graphs. I doubt the latter has an elementary closed form, so that's as far as it goes. We could solve for $f$, writing the other side as a series of powers of that generating function (minus its constant term $1$), but that's messier without any clear benefit.
answered Jan 31 at 9:32
jmerryjmerry
17k11633
$endgroup$
add a comment |
$begingroup$
It's feasible to reduce the problem to finding an exponential generating function for the number of connected graphs.
Let $C(j,l,k)$ be the number of graphs on $j$ labeled vertices and $l$ edges with $k$ components. Use the convention that an empty graph has zero components, so $C(0,0,0)=1$ and $C(0,l,k)=0$ for all other $l,k$.
Consider the component containing vertex $1$ in a graph of $n$ vertices, $m$ edges, and $k$ components. If that component has $j$ vertices and $l$ edges, there are $n-j$ vertices and $m-l$ edges left for the remaining $k-1$ components, so
begin{align*}C(n,m,k) &= sum_{1in Ssubset [n]}sum_l C(|S|,l,1)cdot C(n-|S|,m-l,k-1)\
&= sum_jsum_lbinom{n}{j}C(j,l,1)cdot C(n-j,m-l,k-1)end{align*}
Our choice to put $1$ in the first component means $jge 1$ - but since $C(0,l,1)=0$, we can add $j=0$ back in and just sum over all $j$. Back to the issue at hand - yeah, that looks like an exponential-type convolution. Define $B(n,m,k)=frac1{n!}C(n,m,k)$, and it becomes
$$B(n,m,k)=sum_jsum_l B(j,l,1)cdot B(n-j,m-l,k-1)$$
Now define $f_k(x,y)=sum_nsum_mB(n,m,k)x^ny^m$. Our relation for the $B$ becomes
$$f_k(x,y)=f_1(x,y)cdot f_{k-1}(x,y)$$
so $f_k(x,y)=left(f_1(x,y)right)^k$. Whatever the exponential generating function for connected graphs is, we raise it to the $k$th power to get the exponential generating function for $k$-component graphs.
OK, one more thing. Since every graph has some number of connected components, we can sum over $k$:
$$frac1{1-f(x,y)} = sum_k f^k(x,y) = sum_{m,n}frac1{n!}binom{binom{n}{2}}{m}x^ny^m = sum_nfrac{x^n}{n!}(1+y)^{n(n-1)/2}$$
where $f$ is the EGF for the number of connected graphs and the right hand side is the EGF for the number of total graphs. I doubt the latter has an elementary closed form, so that's as far as it goes. We could solve for $f$, writing the other side as a series of powers of that generating function (minus its constant term $1$), but that's messier without any clear benefit.
answered Jan 31 at 9:32
jmerryjmerry
17k11633
$endgroup$
add a comment |
$begingroup$
It's feasible to reduce the problem to finding an exponential generating function for the number of connected graphs.
Let $C(j,l,k)$ be the number of graphs on $j$ labeled vertices and $l$ edges with $k$ components. Use the convention that an empty graph has zero components, so $C(0,0,0)=1$ and $C(0,l,k)=0$ for all other $l,k$.
Consider the component containing vertex $1$ in a graph of $n$ vertices, $m$ edges, and $k$ components. If that component has $j$ vertices and $l$ edges, there are $n-j$ vertices and $m-l$ edges left for the remaining $k-1$ components, so
begin{align*}C(n,m,k) &= sum_{1in Ssubset [n]}sum_l C(|S|,l,1)cdot C(n-|S|,m-l,k-1)\
&= sum_jsum_lbinom{n}{j}C(j,l,1)cdot C(n-j,m-l,k-1)end{align*}
Our choice to put $1$ in the first component means $jge 1$ - but since $C(0,l,1)=0$, we can add $j=0$ back in and just sum over all $j$. Back to the issue at hand - yeah, that looks like an exponential-type convolution. Define $B(n,m,k)=frac1{n!}C(n,m,k)$, and it becomes
$$B(n,m,k)=sum_jsum_l B(j,l,1)cdot B(n-j,m-l,k-1)$$
Now define $f_k(x,y)=sum_nsum_mB(n,m,k)x^ny^m$. Our relation for the $B$ becomes
$$f_k(x,y)=f_1(x,y)cdot f_{k-1}(x,y)$$
so $f_k(x,y)=left(f_1(x,y)right)^k$. Whatever the exponential generating function for connected graphs is, we raise it to the $k$th power to get the exponential generating function for $k$-component graphs.
OK, one more thing. Since every graph has some number of connected components, we can sum over $k$:
$$frac1{1-f(x,y)} = sum_k f^k(x,y) = sum_{m,n}frac1{n!}binom{binom{n}{2}}{m}x^ny^m = sum_nfrac{x^n}{n!}(1+y)^{n(n-1)/2}$$
where $f$ is the EGF for the number of connected graphs and the right hand side is the EGF for the number of total graphs. I doubt the latter has an elementary closed form, so that's as far as it goes. We could solve for $f$, writing the other side as a series of powers of that generating function (minus its constant term $1$), but that's messier without any clear benefit.
answered Jan 31 at 9:32
jmerryjmerry
17k11633
$endgroup$
It's feasible to reduce the problem to finding an exponential generating function for the number of connected graphs.
Let $C(j,l,k)$ be the number of graphs on $j$ labeled vertices and $l$ edges with $k$ components. Use the convention that an empty graph has zero components, so $C(0,0,0)=1$ and $C(0,l,k)=0$ for all other $l,k$.
Consider the component containing vertex $1$ in a graph of $n$ vertices, $m$ edges, and $k$ components. If that component has $j$ vertices and $l$ edges, there are $n-j$ vertices and $m-l$ edges left for the remaining $k-1$ components, so
begin{align*}C(n,m,k) &= sum_{1in Ssubset [n]}sum_l C(|S|,l,1)cdot C(n-|S|,m-l,k-1)\
&= sum_jsum_lbinom{n}{j}C(j,l,1)cdot C(n-j,m-l,k-1)end{align*}
Our choice to put $1$ in the first component means $jge 1$ - but since $C(0,l,1)=0$, we can add $j=0$ back in and just sum over all $j$. Back to the issue at hand - yeah, that looks like an exponential-type convolution. Define $B(n,m,k)=frac1{n!}C(n,m,k)$, and it becomes
$$B(n,m,k)=sum_jsum_l B(j,l,1)cdot B(n-j,m-l,k-1)$$
Now define $f_k(x,y)=sum_nsum_mB(n,m,k)x^ny^m$. Our relation for the $B$ becomes
$$f_k(x,y)=f_1(x,y)cdot f_{k-1}(x,y)$$
so $f_k(x,y)=left(f_1(x,y)right)^k$. Whatever the exponential generating function for connected graphs is, we raise it to the $k$th power to get the exponential generating function for $k$-component graphs.
OK, one more thing. Since every graph has some number of connected components, we can sum over $k$:
$$frac1{1-f(x,y)} = sum_k f^k(x,y) = sum_{m,n}frac1{n!}binom{binom{n}{2}}{m}x^ny^m = sum_nfrac{x^n}{n!}(1+y)^{n(n-1)/2}$$
where $f$ is the EGF for the number of connected graphs and the right hand side is the EGF for the number of total graphs. I doubt the latter has an elementary closed form, so that's as far as it goes. We could solve for $f$, writing the other side as a series of powers of that generating function (minus its constant term $1$), but that's messier without any clear benefit.
answered Jan 31 at 9:32
jmerryjmerry
17k11633
edited Jan 31 at 11:21
answered Jan 31 at 9:32
jmerryjmerry
17k11633
answered Jan 31 at 9:32
jmerryjmerry
17k11633
answered Jan 31 at 9:32
jmerryjmerry
17k11633
17k11633
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3094635%2fgenerating-function-for-the-number-of-graphs-with-k-connected-components%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
Some material to consult at this MSE link.
$endgroup$
– Marko Riedel
Jan 31 at 15:05
$begingroup$
Can you clarify: $a_k$ is the number of graphs on $n$ vertices with $m$ edges and $k$ components? And you want to find $sum_{k=0}^{n}a_kfrac{x^k}{k!}$?
$endgroup$
– Mike Earnest
Jan 31 at 16:30
$begingroup$
@MikeEarnest Correct.
$endgroup$
– Teddy
Feb 3 at 7:26