4 ms·
This work is subtly related to chaos theory. The nth coefficient of the ith Mandelbrot polynomial lemniscate [3] is equal to the number of possible binary tree
by goldenkey 4y ago
This work is subtly related to chaos theory.
The nth coefficient of the ith Mandelbrot polynomial lemniscate [3] is equal to the number of possible binary trees with n nodes of height i or less. This is because z -> z^2 + c reflects coefficients recursively produced by repeated applications of the binomial theorem.
When n becomes <= i, the nth coefficient stabilizes, converging to the nth Catalan number, which is the number of possible binary trees with n nodes. The nth Catalan number is also the number of triangulations of an n+2-gon.
https://en.m.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics https://en.m.wikipedia.org/wiki/Catalan_number#Applications_...
Now, there is a 1-to-1 bijective mapping between binary trees of height n and node count i, and n+2 sided polygon triangulations with i segments.
https://www.r-bloggers.com/2015/07/catalan-numbers-fortriangulationsgamblers-ruinbinary/ https://www.r-bloggers.com/2015/07/catalan-numbers-fortriang...
In fact, the same associahedron in "Flipping until you are lost" is mentioned here:
https://www.researchgate.net/figure/The-bijection-between-binary-plane-trees-and-triangulations-of-a-polygon-as_fig1_225917464 https://www.researchgate.net/figure/The-bijection-between-bi...
What is the significance of all of this? There is currently no closed form approximation for these numbers. As simple as it might sound, we have no closed form for the number of binary trees with i nodes of height <= n. If we did, we could approximate the Mandelbrot and it would unlock new frontiers of understanding chaos theory.
Philippe Flajolet, a now-deceased titan of analytic combinatorics [2] wrote some papers on the problem, but never got more than rough asymptotic bounds.
https://www.sciencedirect.com/science/article/pii/0022000082900046 https://www.sciencedirect.com/science/article/pii/0022000082...
Further work was done here: https://www.labri.fr/Perso/~bousquet/Exposes/trees.pdf https://www.labri.fr/Perso/~bousquet/Exposes/trees.pdf
When I saw this, my eyes lit up. It is late but in the morning I will have to see if the findings in this paper help at all with the above problem.
-------
[1] https://en.wikipedia.org/wiki/Philippe_Flajolet https://en.wikipedia.org/wiki/Philippe_Flajolet
[2] https://en.wikipedia.org/wiki/Symbolic_method_(combinatorics) https://en.wikipedia.org/wiki/Symbolic_method_(combinatorics...
[3] http://www.mrob.com/pub/muency/lemniscates.html http://www.mrob.com/pub/muency/lemniscates.html