Book

Math

Discovery

Andrius Kulikauskas

  • ms@ms.lt
  • +370 607 27 665
  • My work is in the Public Domain for all to share freely.

Lietuvių kalba

Understandable FFFFFF

Questions FFFFC0

Notes EEEEEE

Software

Žr. Matematika?

Consider how to relate the Catalan generating function to a complex number and a context-free grammar.

Consider their being k break points in the terms of the kth Mandelbrot polynomial, consider them as flip points for going between outside and inside.

How does binary tree height correspond to the difference between left-right parentheses?

Look at q-catalan numbers. How do they relate to parentheses discrepancy?

What are the q-t-catalan numbers, what do they count, and how do they relate to the Macdonald polynomials?

Consider how to relate the boundedness of the generating function to the idea that there is a finite mismatch between left and right parentheses, whereas if the number of left parentheses grows without bound, then the function diverges to infinity.

Consider what we know about the boundedness of the generating function in the complex plane.

Dievas: walks on binary trees (C,I,U). Ar tai tas pats kaip "ordered binary trees"? Ar juos skaičiuoja Catalan skaičiai?

  • There is one correct progression: C->I->U->C... Do the convergent sequences represent finite mistakes which are corrected. And then is there a distinction between finite (bounded) and infinite (divergent) mistakes?

Jeigu pridėti c + d (delta) ką sužinotumėme apie mažą paklaidą?

The issue of memory required by automata - that this is "explicit" truth needed to supplement "implicit" truth.

Analytic Combinatorics by Philippe Flajolet, Robert Sedgewick, 2009. They briefly mention the connection between Mandelbrot sets and Catalan numbers as noting "the speed of convergence" for "the generating functions of binary trees of bounded height". Look for Catalan numbers:

  • Section V.2 - supercritical sequence schema: compositions, surjections, alignments. (Regard in terms of duality of top-down and bottom-up, addition and partition.)
  • Section V.3 - regular expressions as by regular automata (Figure V.5 on asymptotics).
  • Section V.4 - lattice paths as by context-free grammars, Continued Fraction Theorem. See especially the figure linking V.11 linking objects, weights, counting numbers (Catlan numbers), orthogonal polynomials (Chebyshev).
  • see also 279 exponential growth for tree families, including 3, e, 4.
  • Transfer matrix models
  • VI.18 Tolls and costs for Binary tree recurrence. "This example is also of interest since it furnishes an analytically tractable model of a coalescence-fragmentation process, which is of great interest in several areas of science, for which we refer to Aldous’ survey [9]."
  • VII.3.1 Asymptotic counting
  • Proposition VII.2 links between tree types and probability distributions.
  • Theorem VII.6 on Irreducible positive polynomial systems.
  • VII.27 Catalan and Jacobian determinant
  • Figure VII.16 Catalan curve
  • VII.21 Trees and Lukasiewicz codes
  • VII.27 Height of binary trees, mentions Mandelbrot set. Each polynomial has degree 2^(h-1)-1. "When
 |z| ≤ r < 1/4, 

simple majorant series considerations show that the convergence

 yh(z)→y(z) 

is uniformly geometric. When

 z ≥ s > 1/4

it can be checked that the yh(z) grow doubly exponentially. What happens in-between, in a delta–domain, needs to be quantified. We do so following Flajolet, Gao, Odlyzko, and Richmond [230, 246]. (They analyze the convergence in the interesting domain.)

  • Figure VII.24 A collection of universality laws.
  • Page 538 Nice relation of tree heights for different kinds of trees.
  • Figure IX.13 Singularities of generating functions of Catalan trees, square-root type.
  • [230] Flajolet, P., Gao, Z.,Odlyzko, A.,M., and Richmond, B. The distribution of heights of binary trees and other simple trees. Combinatorics, Probability and Computing 2 (1993), 145–15
  • [246] Flajolet, P.,Odlyzko, A.,M. The average height of binary trees and other simple trees. Journal of Computer and System Sciences 25 (1982), 171–213

It seems that the Catalan numbers serve to count both of these cases:

  • Any well ordered string of parentheses.
  • Only those well ordered strings of parentheses that have no superluous (repeated) parentheses. (Full binary trees.)
  • And also this case: of all ordered trees.

Whereas "all binary trees" (all parentheses) are given by binomial theorem, as can be seen by expanding ( + ) to the N.

Mandelbrot set rule: The simplest "mixing rule": "Add the input (complex vector c), add the output ("multiply by 2" by complex rotating and squaring)."

The $q,t$-Catalan Numbers and the Space of Diagonal Harmonics (University Lecture Series) by James Haglund. With an appendix on the MacDonald polynomials (linked to root weights).

Square root as a sign of "dual" mid-point (reflection point) in a duality.

Catalan


Naujausi pakeitimai


Puslapis paskutinį kartą pakeistas 2017 gruodžio 09 d., 17:37
Tweet