STATUS: Draft
# Non standard depencies
# !pip install -U treelib
# !pip install tskit
import numpy as np
import sympy as sp
import pickle
from IPython.display import HTML, SVG
import ipywidgets as widgets
import matplotlib as mpl
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
mpl.rcParams['legend.fontsize'] = 10
import pandas as pd
import itertools
pd.set_option('display.max_colwidth', None)
import treelib as tr
import tskit as ts
# function to print latex
def renderListToLatex(e):
latex_rendering = []
for i in range(len(e)):
latex_rendering.append("$$" + sp.latex(e[i]) + "$$<br/>")
return(HTML("".join(latex_rendering[0:])))
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$.
def F1(m2, m3, returnCoefficientsOnly = False, returnCoefficientsOnlyWithoutSigns = True, returnCoefficientsAsFactorialStrings = False):
c_0, c_1, c_2, c_3 = sp.symbols('c_0, c_1, c_2, c_3')
s1 = (-1)**(m3 + 1)
s2 = sp.factorial(2 * m2 + 3 * m3)
s3 = sp.factorial(1 + m2 + 2 * m3) * sp.factorial(m2) * sp.factorial(m3)
s4 = c_0**(1 + m2 + 2 * m3) * c_2**m2 *c_3**m3
s5 = c_1**(2 * m2 + 3 * m3 + 1)
s7 = str(2 * m2 + 3 * m3) + "!"
s8 = str(1 + m2 + 2 * m3) + "!" + str(m2) + "!" + str(m3) + "!"
if returnCoefficientsOnly:
s6 = s1 * (s2 / s3)
elif returnCoefficientsOnlyWithoutSigns:
s6 = (s2 / s3)
elif returnCoefficientsAsFactorialStrings:
s6 = str(s7 + " | " + s8)
else:
s6 = s1 * (s2 / s3) * (s4 / s5)
return(s6)
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!}$
P1 = np.arange(8)
P2 = np.array([[F1(j, i) for i in P1] for j in P1])
P3 = sp.Matrix(P2)
P3
Let $F2$ be a function that implements $(2 + m + 2n)$. which generates the number of sides of different polygons.
def F2(m, n):
return(2 + m + 2 * n)
P4 = np.arange(8)
P5 = np.array([[F2(j, i) for i in P4] for j in P4])
P6 = sp.Matrix(P5)
P6
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
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
tree = tr.Tree()
tree.create_node("1", "1") # root node
tree.create_node("2", "2", parent="1")
tree.create_node("3", "3", parent="1")
tree.create_node("4", "4", parent="2")
tree.create_node("5", "5", parent="2")
tree.show()
tree = tr.Tree()
tree.create_node("1", "1") # root node
tree.create_node("2", "2", parent="1")
tree.create_node("3", "3", parent="1")
tree.create_node("4", "4", parent="3")
tree.create_node("5", "5", parent="3")
tree.show()
1 ├── 2 │ ├── 4 │ └── 5 └── 3 1 ├── 2 └── 3 ├── 4 └── 5
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
def allbinarytrees(s):
if len(s) == 1:
yield s
else:
for i in range(1, len(s), 2):
for l in allbinarytrees(s[:i]):
for r in allbinarytrees(s[i+1:]):
yield '({}{}{})'.format(l, s[i], r)
for t in allbinarytrees('1-2-3-4'):
print(t)
# Note - this function to create tree combinations
def allbinarytrees(s):
if len(s) == 1:
yield s
else:
for i in range(1, len(s), 2):
for l in allbinarytrees(s[:i]):
for r in allbinarytrees(s[i+1:]):
yield '({}{}{})'.format(l, s[i], r)
for t in allbinarytrees('1-2-3-4'):
print(t)
(1-(2-(3-4))) (1-((2-3)-4)) ((1-2)-(3-4)) ((1-(2-3))-4) (((1-2)-3)-4)
# This version for arbitrary length labels
def allbinarytrees(s):
if s.isdigit():
yield s
else:
i = 0
while i < len(s)-1:
while i < len(s) and s[i].isdigit():
i += 1
if i < len(s) - 1:
for left in allbinarytrees(s[:i]):
for right in allbinarytrees(s[i+1:]):
yield '({}{}{})'.format(left, s[i], right)
i += 1
j=0
for t in allbinarytrees('11+22*3/4456'):
j += 1
print(j, (t[1:-1]))
1 11+(22*(3/4456)) 2 11+((22*3)/4456) 3 (11+22)*(3/4456) 4 (11+(22*3))/4456 5 ((11+22)*3)/4456