How to Generate a Function for Vertex Distance in a Planar Tree?

In summary, a Generating Function Tree is a graphical representation of a generating function, used in combinatorics and analysis. It is constructed by recursively applying rules to the original function and is useful for solving problems involving generating functions. It has applications in mathematics, computer science, physics, and engineering, but may have limitations with non-linear functions and multiple variables.
  • #1
Howang
1
0
Hi,

Please I need you help to solve this problem:

----------

Consider a planar tree with $n$ non-root vertices (root edge selected).

1. Give a generating function for vertices distance $d$ from the root.
2. Proof that the total number is $$\displaystyle \binom{2n}{n-d}\frac{2d+1}{(n+d+1)}$$

----------

We are supposed to have an exponential generating function then use Lagrange Inversion Theorem.
 
Physics news on Phys.org
  • #2
Hello there, Howang! :D

Have you managed a partial proof, or made any inroads into solving this problem? If so, please DO share.

Thanks!

Gethin
 

FAQ: How to Generate a Function for Vertex Distance in a Planar Tree?

What is a Generating Function Tree?

A Generating Function Tree is a graphical representation of a generating function, which is a mathematical tool used in combinatorics and analysis to describe a sequence of numbers. It is a tree structure that shows how a sequence can be broken down into smaller subsequences and their respective generating functions.

How is a Generating Function Tree constructed?

A Generating Function Tree is constructed by recursively applying a set of rules to the original generating function until it is broken down into simpler functions. Each level of the tree corresponds to a different degree of the generating function, with the root being the original function and the leaves being the simplest functions.

What is the purpose of a Generating Function Tree?

The purpose of a Generating Function Tree is to provide a systematic way of solving problems involving generating functions. It allows for the identification of patterns and simplification of complex functions, making it easier to calculate coefficients and analyze the behavior of a sequence.

What are some applications of Generating Function Trees?

Generating Function Trees have many applications in mathematics and computer science, including counting problems, probability calculations, and algorithm analysis. They are also used in physics and engineering to solve problems involving recurrence relations and differential equations.

What are some limitations of Generating Function Trees?

Generating Function Trees are limited in their ability to solve problems involving non-linear generating functions or those with multiple variables. They also require a good understanding of generating functions and their properties to be used effectively. Additionally, they may become complex and difficult to interpret for large or highly nested generating functions.

Similar threads

MHB Graph Grammer Function For Two Exotic Graphs Question please.
Replies
4
Views
2K
There are effectively computable numerical functions which aren’t prim
Replies
1
Views
1K
Function Generator for Sequences of Reals
Replies
24
Views
3K
MHB Log-concave posterior density function adaptive rejection sampling
Replies
1
Views
1K
I On inverse function theorem in Spivak's CoM
Replies
6
Views
1K
MHB What is the Time Complexity of this Vertex Cover Algorithm?
Replies
1
Views
1K
MATLAB code for Aldous-Broder algorithm from spanning trees of a graph
Replies
4
Views
3K
MHB A decision tree has an expected depth of at least log n
Replies
1
Views
1K
A Recover Hamilton equation from 2-form defined on phase space
Replies
3
Views
720
Precalculus knowledge for learning Discrete Math CS topics?
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top