Deep understanding on exponential generating function












3












$begingroup$


In spite of having done some exercises, I still find it harder to understand exponential generating function deeply than ordinary generating function. Could someone explain it "deeply"? Or are there any articles on that?










share|cite|improve this question









$endgroup$












  • $begingroup$
    I suggest that you either read the book by Bergeron, Labelle and Leroux or that you ask a more precise question. The book might help to convince you that egfs are simpler than ogfs. books.google.com/…
    $endgroup$
    – Phira
    Nov 6 '11 at 0:02








  • 1




    $begingroup$
    I like "Generatingfunctionology" by Wilf. The 2nd edition can be downloaded from math.upenn.edu/~wilf/DownldGF.html. The 3rd edition is available from the publisher.
    $endgroup$
    – marty cohen
    Nov 6 '11 at 0:17






  • 1




    $begingroup$
    Chapter $3$ of Miklós Bóna’s Introduction to Enumerative Combinatorics gives a nice introductory sense of the respective contexts in which egf’s and ogf’s are useful.
    $endgroup$
    – Brian M. Scott
    Nov 6 '11 at 0:23






  • 5




    $begingroup$
    Think of it this way: there are situations where the EGF is simple/easy to manipulate when the OGF is unwieldy or has no closed form, and vice-versa...
    $endgroup$
    – J. M. is not a mathematician
    Nov 6 '11 at 1:08






  • 3




    $begingroup$
    anon guessed correctly, here's an old blog post by Qiaochu somewhat related to this.
    $endgroup$
    – Ragib Zaman
    Nov 6 '11 at 2:19


















3












$begingroup$


In spite of having done some exercises, I still find it harder to understand exponential generating function deeply than ordinary generating function. Could someone explain it "deeply"? Or are there any articles on that?










share|cite|improve this question









$endgroup$












  • $begingroup$
    I suggest that you either read the book by Bergeron, Labelle and Leroux or that you ask a more precise question. The book might help to convince you that egfs are simpler than ogfs. books.google.com/…
    $endgroup$
    – Phira
    Nov 6 '11 at 0:02








  • 1




    $begingroup$
    I like "Generatingfunctionology" by Wilf. The 2nd edition can be downloaded from math.upenn.edu/~wilf/DownldGF.html. The 3rd edition is available from the publisher.
    $endgroup$
    – marty cohen
    Nov 6 '11 at 0:17






  • 1




    $begingroup$
    Chapter $3$ of Miklós Bóna’s Introduction to Enumerative Combinatorics gives a nice introductory sense of the respective contexts in which egf’s and ogf’s are useful.
    $endgroup$
    – Brian M. Scott
    Nov 6 '11 at 0:23






  • 5




    $begingroup$
    Think of it this way: there are situations where the EGF is simple/easy to manipulate when the OGF is unwieldy or has no closed form, and vice-versa...
    $endgroup$
    – J. M. is not a mathematician
    Nov 6 '11 at 1:08






  • 3




    $begingroup$
    anon guessed correctly, here's an old blog post by Qiaochu somewhat related to this.
    $endgroup$
    – Ragib Zaman
    Nov 6 '11 at 2:19
















3












3








3


1



$begingroup$


In spite of having done some exercises, I still find it harder to understand exponential generating function deeply than ordinary generating function. Could someone explain it "deeply"? Or are there any articles on that?










share|cite|improve this question









$endgroup$




In spite of having done some exercises, I still find it harder to understand exponential generating function deeply than ordinary generating function. Could someone explain it "deeply"? Or are there any articles on that?







combinatorics generating-functions






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Nov 5 '11 at 23:40









VladimirVladimir

1,11311231




1,11311231












  • $begingroup$
    I suggest that you either read the book by Bergeron, Labelle and Leroux or that you ask a more precise question. The book might help to convince you that egfs are simpler than ogfs. books.google.com/…
    $endgroup$
    – Phira
    Nov 6 '11 at 0:02








  • 1




    $begingroup$
    I like "Generatingfunctionology" by Wilf. The 2nd edition can be downloaded from math.upenn.edu/~wilf/DownldGF.html. The 3rd edition is available from the publisher.
    $endgroup$
    – marty cohen
    Nov 6 '11 at 0:17






  • 1




    $begingroup$
    Chapter $3$ of Miklós Bóna’s Introduction to Enumerative Combinatorics gives a nice introductory sense of the respective contexts in which egf’s and ogf’s are useful.
    $endgroup$
    – Brian M. Scott
    Nov 6 '11 at 0:23






  • 5




    $begingroup$
    Think of it this way: there are situations where the EGF is simple/easy to manipulate when the OGF is unwieldy or has no closed form, and vice-versa...
    $endgroup$
    – J. M. is not a mathematician
    Nov 6 '11 at 1:08






  • 3




    $begingroup$
    anon guessed correctly, here's an old blog post by Qiaochu somewhat related to this.
    $endgroup$
    – Ragib Zaman
    Nov 6 '11 at 2:19




















  • $begingroup$
    I suggest that you either read the book by Bergeron, Labelle and Leroux or that you ask a more precise question. The book might help to convince you that egfs are simpler than ogfs. books.google.com/…
    $endgroup$
    – Phira
    Nov 6 '11 at 0:02








  • 1




    $begingroup$
    I like "Generatingfunctionology" by Wilf. The 2nd edition can be downloaded from math.upenn.edu/~wilf/DownldGF.html. The 3rd edition is available from the publisher.
    $endgroup$
    – marty cohen
    Nov 6 '11 at 0:17






  • 1




    $begingroup$
    Chapter $3$ of Miklós Bóna’s Introduction to Enumerative Combinatorics gives a nice introductory sense of the respective contexts in which egf’s and ogf’s are useful.
    $endgroup$
    – Brian M. Scott
    Nov 6 '11 at 0:23






  • 5




    $begingroup$
    Think of it this way: there are situations where the EGF is simple/easy to manipulate when the OGF is unwieldy or has no closed form, and vice-versa...
    $endgroup$
    – J. M. is not a mathematician
    Nov 6 '11 at 1:08






  • 3




    $begingroup$
    anon guessed correctly, here's an old blog post by Qiaochu somewhat related to this.
    $endgroup$
    – Ragib Zaman
    Nov 6 '11 at 2:19


















$begingroup$
I suggest that you either read the book by Bergeron, Labelle and Leroux or that you ask a more precise question. The book might help to convince you that egfs are simpler than ogfs. books.google.com/…
$endgroup$
– Phira
Nov 6 '11 at 0:02






$begingroup$
I suggest that you either read the book by Bergeron, Labelle and Leroux or that you ask a more precise question. The book might help to convince you that egfs are simpler than ogfs. books.google.com/…
$endgroup$
– Phira
Nov 6 '11 at 0:02






1




1




$begingroup$
I like "Generatingfunctionology" by Wilf. The 2nd edition can be downloaded from math.upenn.edu/~wilf/DownldGF.html. The 3rd edition is available from the publisher.
$endgroup$
– marty cohen
Nov 6 '11 at 0:17




$begingroup$
I like "Generatingfunctionology" by Wilf. The 2nd edition can be downloaded from math.upenn.edu/~wilf/DownldGF.html. The 3rd edition is available from the publisher.
$endgroup$
– marty cohen
Nov 6 '11 at 0:17




1




1




$begingroup$
Chapter $3$ of Miklós Bóna’s Introduction to Enumerative Combinatorics gives a nice introductory sense of the respective contexts in which egf’s and ogf’s are useful.
$endgroup$
– Brian M. Scott
Nov 6 '11 at 0:23




$begingroup$
Chapter $3$ of Miklós Bóna’s Introduction to Enumerative Combinatorics gives a nice introductory sense of the respective contexts in which egf’s and ogf’s are useful.
$endgroup$
– Brian M. Scott
Nov 6 '11 at 0:23




5




5




$begingroup$
Think of it this way: there are situations where the EGF is simple/easy to manipulate when the OGF is unwieldy or has no closed form, and vice-versa...
$endgroup$
– J. M. is not a mathematician
Nov 6 '11 at 1:08




$begingroup$
Think of it this way: there are situations where the EGF is simple/easy to manipulate when the OGF is unwieldy or has no closed form, and vice-versa...
$endgroup$
– J. M. is not a mathematician
Nov 6 '11 at 1:08




3




3




$begingroup$
anon guessed correctly, here's an old blog post by Qiaochu somewhat related to this.
$endgroup$
– Ragib Zaman
Nov 6 '11 at 2:19






$begingroup$
anon guessed correctly, here's an old blog post by Qiaochu somewhat related to this.
$endgroup$
– Ragib Zaman
Nov 6 '11 at 2:19












1 Answer
1






active

oldest

votes


















1












$begingroup$

We typically use ordinary generating functions when counting unlabelled objects and exponentially generating functions when counting labelled objects. For instance combinatorial enumeration of permutations is most convenient analysed by exponential generating functions.



Here I'd like to give an indication which structures do we count when applying the binomial convolution
begin{align*}
sum_{k=0}^nbinom{n}{k}b_kc_{n-k}
end{align*}

of two exponential generating functions $B(z)=sum_{j=0}^infty b_j frac{z^j}{j!}$ and $C(z)=sum_{k=0}^infty c_kfrac{z^k}{k!}$.




Permutations:
We introduce a universe $mathcal{P}$ of (labelled) permutations. We label the atoms of the permutations of size $n$ as usual with $1,2,ldots,n$. We also add an empty permutation $varepsilon$ of length $0$ and consider
begin{align*}
mathcal{P}={varepsilon,1,12,21,123,132,213,231,312,321,ldots}tag{1}
end{align*}



The coefficients $a_n$ of the corresponding exponential generating function $A(z)=sum_{n=0}^infty a_n frac{z^n}{n!}$ give the number $n!$ of permutations of size $n$. We obtain
begin{align*}
color{blue}{A(z)}=sum_{n=0}^infty n!frac{z^n}{n!}=sum_{n=0}^infty z^ncolor{blue}{=frac{1}{1-z}}
end{align*}




  • We observe that generating functions like $frac{1}{1-z}$ may serve as both, ordinary generating functions
    begin{align*}
    frac{1}{1-z}=sum_{n=0}^infty z^n=color{blue}{1}+color{blue}{1}cdot z+color{blue}{1}cdot z^2+color{blue}{1}cdot z^3+cdots
    end{align*}

    to count for instance a sequence of unary words
    begin{align*}
    mathcal{S}={varepsilon,bullet,bulletbullet,bulletbulletbullet,ldots}tag{2}
    end{align*}


  • as well as exponential generating functions
    begin{align*}
    frac{1}{1-z}=sum_{n=0}^infty n!frac{z^n}{n!}=color{blue}{0!}+color{blue}{1!}cdot frac{z}{1!}+color{blue}{2!}cdot frac{z^2}{2!}+color{blue}{3!}cdot frac{z^3}{3!}+cdots
    end{align*}

    to count permutations according to (1).


  • Note, the simplicity of the geometric series $frac{1}{1-z}=1+z+z^2+cdots$ strongly indicates the universe of permutations is the prototypical structure approachable by exponential generating functions.





Warmup: Multiplicative structure of ordinary generating functions.



We consider $mathcal{B}={bullet,bulletbulletbullet},mathcal{C}={bullet,bulletbullet}$ with corresponding generating functions $B(z)=z+z^3, C(z)=z+z^2$ and obtain due to the multiplicative rule
begin{align*}
color{blue}{mathrm{card}left(mathcal{B}times mathcal{C}right)=mathrm{card}left(mathcal{B}right)cdot mathrm{card}left(mathcal{C}right)}
end{align*}

the set $mathcal{A}={(bullet,bullet),(bullet,bulletbullet),(bulletbulletbullet,bullet),(bulletbulletbullet,bulletbullet)}$ and the following relationship
begin{align*}
A(z)&=sum_{ainmathcal{A}}z^{|a|}=sum_{(beta,gamma)in(mathcal{B}timesmathcal{C})}z^{|beta|+|gamma|}
=left(sum_{betain mathcal{B}}z^{|beta|}right)timesleft(sum_{gammain mathcal{C}}z^{|C|}right)=B(z)cdot C(z)\
A(z)&=z^2+z^3+z^4+z^5\
&=z^{1+1}+z^{1+2}+z^{3+1}+z^{3+2}=left(z^1+z^3right)timesleft(z^1+z^2right)=(z+z^3)(z+z^2)
end{align*}

which follows from distributing products over sums.




Multiplicative structure of exponential generating functions:



In order to cover the binomial convolution $sum_{k=0}^nbinom{n}{k}b_kc_{n-k}$ of exponential generating functions we will encounter a more sophisticated multiplicative rule for labelled structures. Nevertheless we will do it similarly to the warmup above.



We consider $mathcal{B}={123,213},mathcal{C}={12}$ with generating functions $B(z)=2frac{z^3}{3!}, C(z)=frac{z^2}{2!}$ and consider the multiplicative rule
begin{align*}
color{blue}{mathcal{B}starmathcal{C}=bigcup_{betainmathcal{B},gammainmathcal{C}}left(betastargammaright)}tag{3}
end{align*}

which is defined as:




  • The labelled product (3) of $mathcal{B}$ and $mathcal{C}$, denoted $mathcal{B}starmathcal{C}$, is obtained by forming ordered pairs from $Bstar C$ and performing all possible order-consistent relabellings.




The last phrase all possible order-consistent relabellings needs to be explained.
With the example $mathcal{B}={123,213}$ and $mathcal{C}={12}$ we perform a relabeling.



At first we start with a relabelling and select wlog $mathcal{C}={45}$ by respecting the order ($1<2$, i.e. $4<5$). We now obtain all order-consistent relabellings as follows
begin{align*}
mathcal{B}starmathcal{C}&=bigcup_{betainmathcal{B},gammainmathcal{C}}left(betastargammaright)\
&=left({123}star{45}right)cupleft({213}star{45}right)\
&={12345,12435,12534,13425,13524,14523,23415,23514,24513,34512}tag{4}\
&qquadcup{21345,21435,21534,31425,31524,41523,32415,32514,42513,43512}tag{5}\
end{align*}



When looking at the set ${123}star{45}$ we can find all order-consistent relabelings as follows: We have to generate permutations of length $5$. We create all $binom{5}{3}=10$ strings of length $3$ from ${1,2,3,4,5}$ which follow the order $1<2<3$. We obtain
begin{align*}
{123,124,125,134,135,145,234,235,245,345}.
end{align*}

Note, that each element in the set above follows the ordering $(mathrm{smallest} < mathrm{middle} < mathrm {largest})$. We complete (4) by concatenating each $3$-element string with a string consisting of the remaining two elements from ${1,2,3,4,5}$ following the order $4<5$, i.e. $(mathrm{smallest} < mathrm{largest})$. Similarly we build (5) by respecting the order $2<1<3$, i.e. $(mathrm{middle} < mathrm{smallest} < mathrm{largest})$.




We observe from (4), (5):



begin{align*}
|mathcal{B}starmathcal{C}|=2binom{5}{3}=2cdot 10=20
end{align*}



and the relationship with the generating functions $B(z)$ and $C(z)$ is given as
begin{align*}
color{blue}{A(z)}&=B(z)cdot C(z)=left(2cdot frac{z^3}{3!}right)cdotleft(frac{z^2}{2!}right)\
&,,color{blue}{=2binom{5}{3}frac{z^5}{5!}}
end{align*}




Hint: This answer is based upon the great presentation of admissible structures in chapter 1 and 2 of Analytic Combinatorics by P. Flajolet and R. Sedgewick.






share|cite|improve this answer











$endgroup$














    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
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f79355%2fdeep-understanding-on-exponential-generating-function%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









    1












    $begingroup$

    We typically use ordinary generating functions when counting unlabelled objects and exponentially generating functions when counting labelled objects. For instance combinatorial enumeration of permutations is most convenient analysed by exponential generating functions.



    Here I'd like to give an indication which structures do we count when applying the binomial convolution
    begin{align*}
    sum_{k=0}^nbinom{n}{k}b_kc_{n-k}
    end{align*}

    of two exponential generating functions $B(z)=sum_{j=0}^infty b_j frac{z^j}{j!}$ and $C(z)=sum_{k=0}^infty c_kfrac{z^k}{k!}$.




    Permutations:
    We introduce a universe $mathcal{P}$ of (labelled) permutations. We label the atoms of the permutations of size $n$ as usual with $1,2,ldots,n$. We also add an empty permutation $varepsilon$ of length $0$ and consider
    begin{align*}
    mathcal{P}={varepsilon,1,12,21,123,132,213,231,312,321,ldots}tag{1}
    end{align*}



    The coefficients $a_n$ of the corresponding exponential generating function $A(z)=sum_{n=0}^infty a_n frac{z^n}{n!}$ give the number $n!$ of permutations of size $n$. We obtain
    begin{align*}
    color{blue}{A(z)}=sum_{n=0}^infty n!frac{z^n}{n!}=sum_{n=0}^infty z^ncolor{blue}{=frac{1}{1-z}}
    end{align*}




    • We observe that generating functions like $frac{1}{1-z}$ may serve as both, ordinary generating functions
      begin{align*}
      frac{1}{1-z}=sum_{n=0}^infty z^n=color{blue}{1}+color{blue}{1}cdot z+color{blue}{1}cdot z^2+color{blue}{1}cdot z^3+cdots
      end{align*}

      to count for instance a sequence of unary words
      begin{align*}
      mathcal{S}={varepsilon,bullet,bulletbullet,bulletbulletbullet,ldots}tag{2}
      end{align*}


    • as well as exponential generating functions
      begin{align*}
      frac{1}{1-z}=sum_{n=0}^infty n!frac{z^n}{n!}=color{blue}{0!}+color{blue}{1!}cdot frac{z}{1!}+color{blue}{2!}cdot frac{z^2}{2!}+color{blue}{3!}cdot frac{z^3}{3!}+cdots
      end{align*}

      to count permutations according to (1).


    • Note, the simplicity of the geometric series $frac{1}{1-z}=1+z+z^2+cdots$ strongly indicates the universe of permutations is the prototypical structure approachable by exponential generating functions.





    Warmup: Multiplicative structure of ordinary generating functions.



    We consider $mathcal{B}={bullet,bulletbulletbullet},mathcal{C}={bullet,bulletbullet}$ with corresponding generating functions $B(z)=z+z^3, C(z)=z+z^2$ and obtain due to the multiplicative rule
    begin{align*}
    color{blue}{mathrm{card}left(mathcal{B}times mathcal{C}right)=mathrm{card}left(mathcal{B}right)cdot mathrm{card}left(mathcal{C}right)}
    end{align*}

    the set $mathcal{A}={(bullet,bullet),(bullet,bulletbullet),(bulletbulletbullet,bullet),(bulletbulletbullet,bulletbullet)}$ and the following relationship
    begin{align*}
    A(z)&=sum_{ainmathcal{A}}z^{|a|}=sum_{(beta,gamma)in(mathcal{B}timesmathcal{C})}z^{|beta|+|gamma|}
    =left(sum_{betain mathcal{B}}z^{|beta|}right)timesleft(sum_{gammain mathcal{C}}z^{|C|}right)=B(z)cdot C(z)\
    A(z)&=z^2+z^3+z^4+z^5\
    &=z^{1+1}+z^{1+2}+z^{3+1}+z^{3+2}=left(z^1+z^3right)timesleft(z^1+z^2right)=(z+z^3)(z+z^2)
    end{align*}

    which follows from distributing products over sums.




    Multiplicative structure of exponential generating functions:



    In order to cover the binomial convolution $sum_{k=0}^nbinom{n}{k}b_kc_{n-k}$ of exponential generating functions we will encounter a more sophisticated multiplicative rule for labelled structures. Nevertheless we will do it similarly to the warmup above.



    We consider $mathcal{B}={123,213},mathcal{C}={12}$ with generating functions $B(z)=2frac{z^3}{3!}, C(z)=frac{z^2}{2!}$ and consider the multiplicative rule
    begin{align*}
    color{blue}{mathcal{B}starmathcal{C}=bigcup_{betainmathcal{B},gammainmathcal{C}}left(betastargammaright)}tag{3}
    end{align*}

    which is defined as:




    • The labelled product (3) of $mathcal{B}$ and $mathcal{C}$, denoted $mathcal{B}starmathcal{C}$, is obtained by forming ordered pairs from $Bstar C$ and performing all possible order-consistent relabellings.




    The last phrase all possible order-consistent relabellings needs to be explained.
    With the example $mathcal{B}={123,213}$ and $mathcal{C}={12}$ we perform a relabeling.



    At first we start with a relabelling and select wlog $mathcal{C}={45}$ by respecting the order ($1<2$, i.e. $4<5$). We now obtain all order-consistent relabellings as follows
    begin{align*}
    mathcal{B}starmathcal{C}&=bigcup_{betainmathcal{B},gammainmathcal{C}}left(betastargammaright)\
    &=left({123}star{45}right)cupleft({213}star{45}right)\
    &={12345,12435,12534,13425,13524,14523,23415,23514,24513,34512}tag{4}\
    &qquadcup{21345,21435,21534,31425,31524,41523,32415,32514,42513,43512}tag{5}\
    end{align*}



    When looking at the set ${123}star{45}$ we can find all order-consistent relabelings as follows: We have to generate permutations of length $5$. We create all $binom{5}{3}=10$ strings of length $3$ from ${1,2,3,4,5}$ which follow the order $1<2<3$. We obtain
    begin{align*}
    {123,124,125,134,135,145,234,235,245,345}.
    end{align*}

    Note, that each element in the set above follows the ordering $(mathrm{smallest} < mathrm{middle} < mathrm {largest})$. We complete (4) by concatenating each $3$-element string with a string consisting of the remaining two elements from ${1,2,3,4,5}$ following the order $4<5$, i.e. $(mathrm{smallest} < mathrm{largest})$. Similarly we build (5) by respecting the order $2<1<3$, i.e. $(mathrm{middle} < mathrm{smallest} < mathrm{largest})$.




    We observe from (4), (5):



    begin{align*}
    |mathcal{B}starmathcal{C}|=2binom{5}{3}=2cdot 10=20
    end{align*}



    and the relationship with the generating functions $B(z)$ and $C(z)$ is given as
    begin{align*}
    color{blue}{A(z)}&=B(z)cdot C(z)=left(2cdot frac{z^3}{3!}right)cdotleft(frac{z^2}{2!}right)\
    &,,color{blue}{=2binom{5}{3}frac{z^5}{5!}}
    end{align*}




    Hint: This answer is based upon the great presentation of admissible structures in chapter 1 and 2 of Analytic Combinatorics by P. Flajolet and R. Sedgewick.






    share|cite|improve this answer











    $endgroup$


















      1












      $begingroup$

      We typically use ordinary generating functions when counting unlabelled objects and exponentially generating functions when counting labelled objects. For instance combinatorial enumeration of permutations is most convenient analysed by exponential generating functions.



      Here I'd like to give an indication which structures do we count when applying the binomial convolution
      begin{align*}
      sum_{k=0}^nbinom{n}{k}b_kc_{n-k}
      end{align*}

      of two exponential generating functions $B(z)=sum_{j=0}^infty b_j frac{z^j}{j!}$ and $C(z)=sum_{k=0}^infty c_kfrac{z^k}{k!}$.




      Permutations:
      We introduce a universe $mathcal{P}$ of (labelled) permutations. We label the atoms of the permutations of size $n$ as usual with $1,2,ldots,n$. We also add an empty permutation $varepsilon$ of length $0$ and consider
      begin{align*}
      mathcal{P}={varepsilon,1,12,21,123,132,213,231,312,321,ldots}tag{1}
      end{align*}



      The coefficients $a_n$ of the corresponding exponential generating function $A(z)=sum_{n=0}^infty a_n frac{z^n}{n!}$ give the number $n!$ of permutations of size $n$. We obtain
      begin{align*}
      color{blue}{A(z)}=sum_{n=0}^infty n!frac{z^n}{n!}=sum_{n=0}^infty z^ncolor{blue}{=frac{1}{1-z}}
      end{align*}




      • We observe that generating functions like $frac{1}{1-z}$ may serve as both, ordinary generating functions
        begin{align*}
        frac{1}{1-z}=sum_{n=0}^infty z^n=color{blue}{1}+color{blue}{1}cdot z+color{blue}{1}cdot z^2+color{blue}{1}cdot z^3+cdots
        end{align*}

        to count for instance a sequence of unary words
        begin{align*}
        mathcal{S}={varepsilon,bullet,bulletbullet,bulletbulletbullet,ldots}tag{2}
        end{align*}


      • as well as exponential generating functions
        begin{align*}
        frac{1}{1-z}=sum_{n=0}^infty n!frac{z^n}{n!}=color{blue}{0!}+color{blue}{1!}cdot frac{z}{1!}+color{blue}{2!}cdot frac{z^2}{2!}+color{blue}{3!}cdot frac{z^3}{3!}+cdots
        end{align*}

        to count permutations according to (1).


      • Note, the simplicity of the geometric series $frac{1}{1-z}=1+z+z^2+cdots$ strongly indicates the universe of permutations is the prototypical structure approachable by exponential generating functions.





      Warmup: Multiplicative structure of ordinary generating functions.



      We consider $mathcal{B}={bullet,bulletbulletbullet},mathcal{C}={bullet,bulletbullet}$ with corresponding generating functions $B(z)=z+z^3, C(z)=z+z^2$ and obtain due to the multiplicative rule
      begin{align*}
      color{blue}{mathrm{card}left(mathcal{B}times mathcal{C}right)=mathrm{card}left(mathcal{B}right)cdot mathrm{card}left(mathcal{C}right)}
      end{align*}

      the set $mathcal{A}={(bullet,bullet),(bullet,bulletbullet),(bulletbulletbullet,bullet),(bulletbulletbullet,bulletbullet)}$ and the following relationship
      begin{align*}
      A(z)&=sum_{ainmathcal{A}}z^{|a|}=sum_{(beta,gamma)in(mathcal{B}timesmathcal{C})}z^{|beta|+|gamma|}
      =left(sum_{betain mathcal{B}}z^{|beta|}right)timesleft(sum_{gammain mathcal{C}}z^{|C|}right)=B(z)cdot C(z)\
      A(z)&=z^2+z^3+z^4+z^5\
      &=z^{1+1}+z^{1+2}+z^{3+1}+z^{3+2}=left(z^1+z^3right)timesleft(z^1+z^2right)=(z+z^3)(z+z^2)
      end{align*}

      which follows from distributing products over sums.




      Multiplicative structure of exponential generating functions:



      In order to cover the binomial convolution $sum_{k=0}^nbinom{n}{k}b_kc_{n-k}$ of exponential generating functions we will encounter a more sophisticated multiplicative rule for labelled structures. Nevertheless we will do it similarly to the warmup above.



      We consider $mathcal{B}={123,213},mathcal{C}={12}$ with generating functions $B(z)=2frac{z^3}{3!}, C(z)=frac{z^2}{2!}$ and consider the multiplicative rule
      begin{align*}
      color{blue}{mathcal{B}starmathcal{C}=bigcup_{betainmathcal{B},gammainmathcal{C}}left(betastargammaright)}tag{3}
      end{align*}

      which is defined as:




      • The labelled product (3) of $mathcal{B}$ and $mathcal{C}$, denoted $mathcal{B}starmathcal{C}$, is obtained by forming ordered pairs from $Bstar C$ and performing all possible order-consistent relabellings.




      The last phrase all possible order-consistent relabellings needs to be explained.
      With the example $mathcal{B}={123,213}$ and $mathcal{C}={12}$ we perform a relabeling.



      At first we start with a relabelling and select wlog $mathcal{C}={45}$ by respecting the order ($1<2$, i.e. $4<5$). We now obtain all order-consistent relabellings as follows
      begin{align*}
      mathcal{B}starmathcal{C}&=bigcup_{betainmathcal{B},gammainmathcal{C}}left(betastargammaright)\
      &=left({123}star{45}right)cupleft({213}star{45}right)\
      &={12345,12435,12534,13425,13524,14523,23415,23514,24513,34512}tag{4}\
      &qquadcup{21345,21435,21534,31425,31524,41523,32415,32514,42513,43512}tag{5}\
      end{align*}



      When looking at the set ${123}star{45}$ we can find all order-consistent relabelings as follows: We have to generate permutations of length $5$. We create all $binom{5}{3}=10$ strings of length $3$ from ${1,2,3,4,5}$ which follow the order $1<2<3$. We obtain
      begin{align*}
      {123,124,125,134,135,145,234,235,245,345}.
      end{align*}

      Note, that each element in the set above follows the ordering $(mathrm{smallest} < mathrm{middle} < mathrm {largest})$. We complete (4) by concatenating each $3$-element string with a string consisting of the remaining two elements from ${1,2,3,4,5}$ following the order $4<5$, i.e. $(mathrm{smallest} < mathrm{largest})$. Similarly we build (5) by respecting the order $2<1<3$, i.e. $(mathrm{middle} < mathrm{smallest} < mathrm{largest})$.




      We observe from (4), (5):



      begin{align*}
      |mathcal{B}starmathcal{C}|=2binom{5}{3}=2cdot 10=20
      end{align*}



      and the relationship with the generating functions $B(z)$ and $C(z)$ is given as
      begin{align*}
      color{blue}{A(z)}&=B(z)cdot C(z)=left(2cdot frac{z^3}{3!}right)cdotleft(frac{z^2}{2!}right)\
      &,,color{blue}{=2binom{5}{3}frac{z^5}{5!}}
      end{align*}




      Hint: This answer is based upon the great presentation of admissible structures in chapter 1 and 2 of Analytic Combinatorics by P. Flajolet and R. Sedgewick.






      share|cite|improve this answer











      $endgroup$
















        1












        1








        1





        $begingroup$

        We typically use ordinary generating functions when counting unlabelled objects and exponentially generating functions when counting labelled objects. For instance combinatorial enumeration of permutations is most convenient analysed by exponential generating functions.



        Here I'd like to give an indication which structures do we count when applying the binomial convolution
        begin{align*}
        sum_{k=0}^nbinom{n}{k}b_kc_{n-k}
        end{align*}

        of two exponential generating functions $B(z)=sum_{j=0}^infty b_j frac{z^j}{j!}$ and $C(z)=sum_{k=0}^infty c_kfrac{z^k}{k!}$.




        Permutations:
        We introduce a universe $mathcal{P}$ of (labelled) permutations. We label the atoms of the permutations of size $n$ as usual with $1,2,ldots,n$. We also add an empty permutation $varepsilon$ of length $0$ and consider
        begin{align*}
        mathcal{P}={varepsilon,1,12,21,123,132,213,231,312,321,ldots}tag{1}
        end{align*}



        The coefficients $a_n$ of the corresponding exponential generating function $A(z)=sum_{n=0}^infty a_n frac{z^n}{n!}$ give the number $n!$ of permutations of size $n$. We obtain
        begin{align*}
        color{blue}{A(z)}=sum_{n=0}^infty n!frac{z^n}{n!}=sum_{n=0}^infty z^ncolor{blue}{=frac{1}{1-z}}
        end{align*}




        • We observe that generating functions like $frac{1}{1-z}$ may serve as both, ordinary generating functions
          begin{align*}
          frac{1}{1-z}=sum_{n=0}^infty z^n=color{blue}{1}+color{blue}{1}cdot z+color{blue}{1}cdot z^2+color{blue}{1}cdot z^3+cdots
          end{align*}

          to count for instance a sequence of unary words
          begin{align*}
          mathcal{S}={varepsilon,bullet,bulletbullet,bulletbulletbullet,ldots}tag{2}
          end{align*}


        • as well as exponential generating functions
          begin{align*}
          frac{1}{1-z}=sum_{n=0}^infty n!frac{z^n}{n!}=color{blue}{0!}+color{blue}{1!}cdot frac{z}{1!}+color{blue}{2!}cdot frac{z^2}{2!}+color{blue}{3!}cdot frac{z^3}{3!}+cdots
          end{align*}

          to count permutations according to (1).


        • Note, the simplicity of the geometric series $frac{1}{1-z}=1+z+z^2+cdots$ strongly indicates the universe of permutations is the prototypical structure approachable by exponential generating functions.





        Warmup: Multiplicative structure of ordinary generating functions.



        We consider $mathcal{B}={bullet,bulletbulletbullet},mathcal{C}={bullet,bulletbullet}$ with corresponding generating functions $B(z)=z+z^3, C(z)=z+z^2$ and obtain due to the multiplicative rule
        begin{align*}
        color{blue}{mathrm{card}left(mathcal{B}times mathcal{C}right)=mathrm{card}left(mathcal{B}right)cdot mathrm{card}left(mathcal{C}right)}
        end{align*}

        the set $mathcal{A}={(bullet,bullet),(bullet,bulletbullet),(bulletbulletbullet,bullet),(bulletbulletbullet,bulletbullet)}$ and the following relationship
        begin{align*}
        A(z)&=sum_{ainmathcal{A}}z^{|a|}=sum_{(beta,gamma)in(mathcal{B}timesmathcal{C})}z^{|beta|+|gamma|}
        =left(sum_{betain mathcal{B}}z^{|beta|}right)timesleft(sum_{gammain mathcal{C}}z^{|C|}right)=B(z)cdot C(z)\
        A(z)&=z^2+z^3+z^4+z^5\
        &=z^{1+1}+z^{1+2}+z^{3+1}+z^{3+2}=left(z^1+z^3right)timesleft(z^1+z^2right)=(z+z^3)(z+z^2)
        end{align*}

        which follows from distributing products over sums.




        Multiplicative structure of exponential generating functions:



        In order to cover the binomial convolution $sum_{k=0}^nbinom{n}{k}b_kc_{n-k}$ of exponential generating functions we will encounter a more sophisticated multiplicative rule for labelled structures. Nevertheless we will do it similarly to the warmup above.



        We consider $mathcal{B}={123,213},mathcal{C}={12}$ with generating functions $B(z)=2frac{z^3}{3!}, C(z)=frac{z^2}{2!}$ and consider the multiplicative rule
        begin{align*}
        color{blue}{mathcal{B}starmathcal{C}=bigcup_{betainmathcal{B},gammainmathcal{C}}left(betastargammaright)}tag{3}
        end{align*}

        which is defined as:




        • The labelled product (3) of $mathcal{B}$ and $mathcal{C}$, denoted $mathcal{B}starmathcal{C}$, is obtained by forming ordered pairs from $Bstar C$ and performing all possible order-consistent relabellings.




        The last phrase all possible order-consistent relabellings needs to be explained.
        With the example $mathcal{B}={123,213}$ and $mathcal{C}={12}$ we perform a relabeling.



        At first we start with a relabelling and select wlog $mathcal{C}={45}$ by respecting the order ($1<2$, i.e. $4<5$). We now obtain all order-consistent relabellings as follows
        begin{align*}
        mathcal{B}starmathcal{C}&=bigcup_{betainmathcal{B},gammainmathcal{C}}left(betastargammaright)\
        &=left({123}star{45}right)cupleft({213}star{45}right)\
        &={12345,12435,12534,13425,13524,14523,23415,23514,24513,34512}tag{4}\
        &qquadcup{21345,21435,21534,31425,31524,41523,32415,32514,42513,43512}tag{5}\
        end{align*}



        When looking at the set ${123}star{45}$ we can find all order-consistent relabelings as follows: We have to generate permutations of length $5$. We create all $binom{5}{3}=10$ strings of length $3$ from ${1,2,3,4,5}$ which follow the order $1<2<3$. We obtain
        begin{align*}
        {123,124,125,134,135,145,234,235,245,345}.
        end{align*}

        Note, that each element in the set above follows the ordering $(mathrm{smallest} < mathrm{middle} < mathrm {largest})$. We complete (4) by concatenating each $3$-element string with a string consisting of the remaining two elements from ${1,2,3,4,5}$ following the order $4<5$, i.e. $(mathrm{smallest} < mathrm{largest})$. Similarly we build (5) by respecting the order $2<1<3$, i.e. $(mathrm{middle} < mathrm{smallest} < mathrm{largest})$.




        We observe from (4), (5):



        begin{align*}
        |mathcal{B}starmathcal{C}|=2binom{5}{3}=2cdot 10=20
        end{align*}



        and the relationship with the generating functions $B(z)$ and $C(z)$ is given as
        begin{align*}
        color{blue}{A(z)}&=B(z)cdot C(z)=left(2cdot frac{z^3}{3!}right)cdotleft(frac{z^2}{2!}right)\
        &,,color{blue}{=2binom{5}{3}frac{z^5}{5!}}
        end{align*}




        Hint: This answer is based upon the great presentation of admissible structures in chapter 1 and 2 of Analytic Combinatorics by P. Flajolet and R. Sedgewick.






        share|cite|improve this answer











        $endgroup$



        We typically use ordinary generating functions when counting unlabelled objects and exponentially generating functions when counting labelled objects. For instance combinatorial enumeration of permutations is most convenient analysed by exponential generating functions.



        Here I'd like to give an indication which structures do we count when applying the binomial convolution
        begin{align*}
        sum_{k=0}^nbinom{n}{k}b_kc_{n-k}
        end{align*}

        of two exponential generating functions $B(z)=sum_{j=0}^infty b_j frac{z^j}{j!}$ and $C(z)=sum_{k=0}^infty c_kfrac{z^k}{k!}$.




        Permutations:
        We introduce a universe $mathcal{P}$ of (labelled) permutations. We label the atoms of the permutations of size $n$ as usual with $1,2,ldots,n$. We also add an empty permutation $varepsilon$ of length $0$ and consider
        begin{align*}
        mathcal{P}={varepsilon,1,12,21,123,132,213,231,312,321,ldots}tag{1}
        end{align*}



        The coefficients $a_n$ of the corresponding exponential generating function $A(z)=sum_{n=0}^infty a_n frac{z^n}{n!}$ give the number $n!$ of permutations of size $n$. We obtain
        begin{align*}
        color{blue}{A(z)}=sum_{n=0}^infty n!frac{z^n}{n!}=sum_{n=0}^infty z^ncolor{blue}{=frac{1}{1-z}}
        end{align*}




        • We observe that generating functions like $frac{1}{1-z}$ may serve as both, ordinary generating functions
          begin{align*}
          frac{1}{1-z}=sum_{n=0}^infty z^n=color{blue}{1}+color{blue}{1}cdot z+color{blue}{1}cdot z^2+color{blue}{1}cdot z^3+cdots
          end{align*}

          to count for instance a sequence of unary words
          begin{align*}
          mathcal{S}={varepsilon,bullet,bulletbullet,bulletbulletbullet,ldots}tag{2}
          end{align*}


        • as well as exponential generating functions
          begin{align*}
          frac{1}{1-z}=sum_{n=0}^infty n!frac{z^n}{n!}=color{blue}{0!}+color{blue}{1!}cdot frac{z}{1!}+color{blue}{2!}cdot frac{z^2}{2!}+color{blue}{3!}cdot frac{z^3}{3!}+cdots
          end{align*}

          to count permutations according to (1).


        • Note, the simplicity of the geometric series $frac{1}{1-z}=1+z+z^2+cdots$ strongly indicates the universe of permutations is the prototypical structure approachable by exponential generating functions.





        Warmup: Multiplicative structure of ordinary generating functions.



        We consider $mathcal{B}={bullet,bulletbulletbullet},mathcal{C}={bullet,bulletbullet}$ with corresponding generating functions $B(z)=z+z^3, C(z)=z+z^2$ and obtain due to the multiplicative rule
        begin{align*}
        color{blue}{mathrm{card}left(mathcal{B}times mathcal{C}right)=mathrm{card}left(mathcal{B}right)cdot mathrm{card}left(mathcal{C}right)}
        end{align*}

        the set $mathcal{A}={(bullet,bullet),(bullet,bulletbullet),(bulletbulletbullet,bullet),(bulletbulletbullet,bulletbullet)}$ and the following relationship
        begin{align*}
        A(z)&=sum_{ainmathcal{A}}z^{|a|}=sum_{(beta,gamma)in(mathcal{B}timesmathcal{C})}z^{|beta|+|gamma|}
        =left(sum_{betain mathcal{B}}z^{|beta|}right)timesleft(sum_{gammain mathcal{C}}z^{|C|}right)=B(z)cdot C(z)\
        A(z)&=z^2+z^3+z^4+z^5\
        &=z^{1+1}+z^{1+2}+z^{3+1}+z^{3+2}=left(z^1+z^3right)timesleft(z^1+z^2right)=(z+z^3)(z+z^2)
        end{align*}

        which follows from distributing products over sums.




        Multiplicative structure of exponential generating functions:



        In order to cover the binomial convolution $sum_{k=0}^nbinom{n}{k}b_kc_{n-k}$ of exponential generating functions we will encounter a more sophisticated multiplicative rule for labelled structures. Nevertheless we will do it similarly to the warmup above.



        We consider $mathcal{B}={123,213},mathcal{C}={12}$ with generating functions $B(z)=2frac{z^3}{3!}, C(z)=frac{z^2}{2!}$ and consider the multiplicative rule
        begin{align*}
        color{blue}{mathcal{B}starmathcal{C}=bigcup_{betainmathcal{B},gammainmathcal{C}}left(betastargammaright)}tag{3}
        end{align*}

        which is defined as:




        • The labelled product (3) of $mathcal{B}$ and $mathcal{C}$, denoted $mathcal{B}starmathcal{C}$, is obtained by forming ordered pairs from $Bstar C$ and performing all possible order-consistent relabellings.




        The last phrase all possible order-consistent relabellings needs to be explained.
        With the example $mathcal{B}={123,213}$ and $mathcal{C}={12}$ we perform a relabeling.



        At first we start with a relabelling and select wlog $mathcal{C}={45}$ by respecting the order ($1<2$, i.e. $4<5$). We now obtain all order-consistent relabellings as follows
        begin{align*}
        mathcal{B}starmathcal{C}&=bigcup_{betainmathcal{B},gammainmathcal{C}}left(betastargammaright)\
        &=left({123}star{45}right)cupleft({213}star{45}right)\
        &={12345,12435,12534,13425,13524,14523,23415,23514,24513,34512}tag{4}\
        &qquadcup{21345,21435,21534,31425,31524,41523,32415,32514,42513,43512}tag{5}\
        end{align*}



        When looking at the set ${123}star{45}$ we can find all order-consistent relabelings as follows: We have to generate permutations of length $5$. We create all $binom{5}{3}=10$ strings of length $3$ from ${1,2,3,4,5}$ which follow the order $1<2<3$. We obtain
        begin{align*}
        {123,124,125,134,135,145,234,235,245,345}.
        end{align*}

        Note, that each element in the set above follows the ordering $(mathrm{smallest} < mathrm{middle} < mathrm {largest})$. We complete (4) by concatenating each $3$-element string with a string consisting of the remaining two elements from ${1,2,3,4,5}$ following the order $4<5$, i.e. $(mathrm{smallest} < mathrm{largest})$. Similarly we build (5) by respecting the order $2<1<3$, i.e. $(mathrm{middle} < mathrm{smallest} < mathrm{largest})$.




        We observe from (4), (5):



        begin{align*}
        |mathcal{B}starmathcal{C}|=2binom{5}{3}=2cdot 10=20
        end{align*}



        and the relationship with the generating functions $B(z)$ and $C(z)$ is given as
        begin{align*}
        color{blue}{A(z)}&=B(z)cdot C(z)=left(2cdot frac{z^3}{3!}right)cdotleft(frac{z^2}{2!}right)\
        &,,color{blue}{=2binom{5}{3}frac{z^5}{5!}}
        end{align*}




        Hint: This answer is based upon the great presentation of admissible structures in chapter 1 and 2 of Analytic Combinatorics by P. Flajolet and R. Sedgewick.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Jan 16 at 10:56

























        answered Jan 16 at 7:06









        Markus ScheuerMarkus Scheuer

        63.6k460152




        63.6k460152






























            draft saved

            draft discarded




















































            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.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f79355%2fdeep-understanding-on-exponential-generating-function%23new-answer', 'question_page');
            }
            );

            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







            Popular posts from this blog

            Human spaceflight

            Can not write log (Is /dev/pts mounted?) - openpty in Ubuntu-on-Windows?

            張江高科駅