1. ## 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 $\displaystyle 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

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

Thus (this step I don't understand)
$\displaystyle T(x,y)=\sum_{T\in{B}} x^{n(T)}y^{z(T)}$
$\displaystyle =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)}$
$\displaystyle =x(y+2T(x,y)+[T(x,y)]^2)$

I'm having trouble understanding how the function is broken down.

2. ## Re: 2-variable Generating Function

Hey I-Think.

Are the sets L and R disjoint?

3. ## 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

4. ## 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?

5. ## 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)

6. ## 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.