STATUS: Draft


Solving Polynomial Equations (16)


Aim: Understand how Catalan and Fuss numbers relate to binary and ternary trees and how these trees can be created from n-gons


Observe: a solution to a general cubic equation

$$C(m_2, m_3) \equiv(-1)^{m_3 + 1} \frac{(2 m_{2} + 3 m_{3})!}{(1 + m_{2} + 2 m_{3})!m_2!m_3!} \frac{c_0^{1 + m_{2} + 2 m_{3}} c_2^{m_2} c_3^{m_3} }{c_1^{2 m_{2} + 3 m_{3} + 1}}$$

Let $F1$ for a function that implements $C$.

Ref: Robert Dickau's pages on Catalan and Fuss numbers with visualisations of polygons and trees.

Observe: It has has been shown in a previous notebook that Catalan numbers can be related to the number of subdivisions of a (2 + m)-gon into triangles

Observe: It has been shown in a previous notebook that Fuss numbers can be related to the number of subdivisions of a (2 + 2n)-gon into quadrilaterals

Observe: When the number of subdivisions takes into account rotation, so there is a notion of fixed top edge

Ref: These ideas begain with Euler

Let $P3$ be a matrix of values retlating the part of the formula that calculates unsigned coefficients: $ \frac{(2 m_{2} + 3 m_{3})!}{(1 + m_{2} + 2 m_{3})!m_2!m_3!}$

Let $F2$ be a function that implements $(2 + m + 2n)$. which generates the number of sides of different polygons.

Observe: Recall from a previous notebook the relationship $P3$ and $P6$ can be interpreted as follows:


Aim: Outline an algorithm by which any Catalan or Fuss Polygon can be converted into a Binary or Ternary Tree

Method: Examine Catalan numbers, then Fuss Numbers


Conjecture: The Catalan numbers relate to the number of unique binary trees that can be created from a given n-gon the number of planar binary trees with n+1 leaves. Note a leaf node is a node with no children nodes

Let: the following a procedure to create a binary tree from polygon

  1. Divide n-gon into any cominbation triangles
  2. Place node inside each triangle
  3. Join adjacent nodes inside n-gon
  4. Create edges from newly created nodes with nodes outside each edge of the polygon. Note that crossing edges within the plane is not allowed
  5. Consider the number of trees that can be created
  6. Divide n-gon into any combination of triangles which has not been carried out.
  7. Repeat process from step 2

Observe: This produces the number of rooted planar binary trees with increasing values of n:

Observe: This can be intuited as follows:

Observe: Every non-leave node has 2 children when rewritten in downward way

Observe: Binary trees provide an important way to manage data in computer science settings and can be used as sorting and searching algorithm

Observe: Ternary Trees are similiar

Observe: This can be intuited as follows:

Observe It is possible to join these two structures toghether and and create a Ternary/Binary (or BiTri tree).

Todo: Find a programatic way to generate all combinations of trees