Convergence of Exponential Generating Functions
$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_{ngeq 0} 2^{n choose 2} frac{x^n}{n!}=text{exp}E_{c}(x)=text{exp}sum_{ngeq1}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?
combinatorics graph-theory generating-functions algebraic-combinatorics
asked Jan 14 at 1:08
S_AlexS_Alex
1879
$endgroup$
add a comment |
$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_{ngeq 0} 2^{n choose 2} frac{x^n}{n!}=text{exp}E_{c}(x)=text{exp}sum_{ngeq1}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?
combinatorics graph-theory generating-functions algebraic-combinatorics
asked Jan 14 at 1:08
S_AlexS_Alex
1879
$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 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 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 at 2:47
add a comment |
$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_{ngeq 0} 2^{n choose 2} frac{x^n}{n!}=text{exp}E_{c}(x)=text{exp}sum_{ngeq1}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?
combinatorics graph-theory generating-functions algebraic-combinatorics
asked Jan 14 at 1:08
S_AlexS_Alex
1879
$endgroup$
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_{ngeq 0} 2^{n choose 2} frac{x^n}{n!}=text{exp}E_{c}(x)=text{exp}sum_{ngeq1}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?
combinatorics graph-theory generating-functions algebraic-combinatorics
combinatorics graph-theory generating-functions algebraic-combinatorics
asked Jan 14 at 1:08
S_AlexS_Alex
1879
asked Jan 14 at 1:08
S_AlexS_Alex
1879
asked Jan 14 at 1:08
S_AlexS_Alex
1879
asked Jan 14 at 1:08
S_AlexS_Alex
1879
asked Jan 14 at 1:08
S_AlexS_Alex
1879
1879
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 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 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 at 2:47
add a comment |
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 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 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 at 2:47
3
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 at 1:47
$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 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 at 2:29
$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 at 2:29
3
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 at 2:47
$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 at 2:47
add a comment |
1 Answer
1
active
oldest
votes
$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}^nbinom{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)$.
answered Jan 14 at 16:41
Mike EarnestMike Earnest
25.5k22151
$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%2f3072744%2fconvergence-of-exponential-generating-functions%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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}^nbinom{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)$.
answered Jan 14 at 16:41
Mike EarnestMike Earnest
25.5k22151
$endgroup$
add a comment |
$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}^nbinom{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)$.
answered Jan 14 at 16:41
Mike EarnestMike Earnest
25.5k22151
$endgroup$
add a comment |
$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}^nbinom{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)$.
answered Jan 14 at 16:41
Mike EarnestMike Earnest
25.5k22151
$endgroup$
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}^nbinom{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)$.
answered Jan 14 at 16:41
Mike EarnestMike Earnest
25.5k22151
answered Jan 14 at 16:41
Mike EarnestMike Earnest
25.5k22151
answered Jan 14 at 16:41
Mike EarnestMike Earnest
25.5k22151
answered Jan 14 at 16:41
Mike EarnestMike Earnest
25.5k22151
25.5k22151
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%2f3072744%2fconvergence-of-exponential-generating-functions%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
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 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 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 at 2:47