Results 1 to 6 of 6

Math Help - 2-variable Generating Function

  1. #1
    Senior Member I-Think's Avatar
    Joined
    Apr 2009
    Posts
    288

    2-variable Generating Function

    I'm having trouble understanding a function, in relation to binary rooted trees
    Def'n: a binary rooted tree is a tree with a root node in which every node has at most two children.
    Def'n: A terminal is a node with no children
    Let T be a tree, B the set of all BRTs, n(T) counts the number of nodes in T, z(T) counts the number of terminals

    Let T(x,y)=\sum_{T\in{B}} x^{n(T)}y^{z(T)}

    Noting the recursive structure of BRTs, let L be the left subtree, R the right subtree

    z(T)= z(L)+z(R) if either L or R not empty, 1 if both are empty
    n(T)= 1+ n(L)+n(R)

    Thus (this step I don't understand)
    T(x,y)=\sum_{T\in{B}} x^{n(T)}y^{z(T)}
    =xy+\sum_{L\in{B}} x^{n(L)}y^{z(L)}+\sum_{R\in{B}} x^{n(R)}y^{z(R)}+\sum_{(L,R)\in{BxB}} x^{n(L)+n(R)}y^{z(L)+z(R)}
    =x(y+2T(x,y)+[T(x,y)]^2)

    I'm having trouble understanding how the function is broken down.
    Help please?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    4,173
    Thanks
    766

    Re: 2-variable Generating Function

    Hey I-Think.

    Are the sets L and R disjoint?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member I-Think's Avatar
    Joined
    Apr 2009
    Posts
    288

    Re: 2-variable Generating Function

    L is the left subtree of the BRT T
    and R is the right subtree of the BRT T.
    So yes they are disjoint
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    4,173
    Thanks
    766

    Re: 2-variable Generating Function

    I should have asked this before, what exactly is T(x,y) measuring? I understand what the other functions are trying to do but I don't understand what T(x,y) is: is this just a vector to calculate both the number of nodes and the number of terminal nodes?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member I-Think's Avatar
    Joined
    Apr 2009
    Posts
    288

    Re: 2-variable Generating Function

    Yes, for a given binary rooted tree T, T(x,y) records the number of nodes in the tree (via x variable) and the number of terminals in the tree (via the y variable)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    4,173
    Thanks
    766

    Re: 2-variable Generating Function

    In terms of your notation, this is really confusing since you it is recursively defined by its written like a one-dimensional algebraic representation that is painful to follow.

    If you could re-write this it would be much appreciated, but can you explain what x and y is vs x^a and y^b? Again the way you have written this is completely confusing as hell and doesn't make much sense.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: March 24th 2012, 11:06 AM
  2. Moment Generating function of a normal variable
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: January 11th 2012, 03:15 PM
  3. [SOLVED] Moment Generating function of a gamma variable
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: January 9th 2012, 01:27 PM
  4. Finding probability function of moment generating function
    Posted in the Advanced Statistics Forum
    Replies: 6
    Last Post: July 4th 2011, 05:03 PM
  5. probability generating function of a poisson random variable
    Posted in the Advanced Statistics Forum
    Replies: 12
    Last Post: June 4th 2007, 03:00 AM

Search Tags


/mathhelpforum @mathhelpforum