Solving Functional Equations Dear to W.T. Tutte using the Naive (yet fullly rigorous!) Guess And Check Method
By Shalosh B. Ekhad and Doron Zeilberger
.pdf
.tex
First Written: March 8, 2024
In his seminal paper ``A census of planar triangulations", published in 1962, the iconic graph theorist (and code-breaker),
W.T. Tutte, spent a few pages to prove that a certain bi-variate generating function that enumerates triangulations, satisfies
a certain functional equation. He then used his genius to actually solve it, giving closed-form solutions to the
enumerating sequences. While the first part, of deriving the functional equation, still needs human ingenuity, the
second part, of solving it, can nowadays be fully automated. Our Maple program, accompanying this paper, Tutte.txt,
can not only solve Tutte's original equation in a few seconds, it can also solve many, far more complicated ones,
way beyond the scope of even such a giant as W.T. Tutte. We use our favorite method of ``guess and check"
and show how it can always be made fully rigorous (if desired).
Maple package
-
Tutte.txt,
a Maple package for automatically solving functional equations dear to W.T. Tutte
Sample Input and Output for Tutte.txt
-
If you want to see a fully rigorous derivation, done in less than a second, of the solutions to the functional equation that took Tutte a long time to solve in his
seminal paper "A Census of Planar Triangulations"
the input gives the
output.
-
If you want to see a fully rigorous derivation, done in 81 seconds, of the solutions to a similar functional equation that we doubt that Tutte would have been able to solve by hand
the input gives the
output.
-
Here is another simpler, example
the input gives the
output.
-
Here is another, far more complicated, example, where it is cubic in Phi(x,y)
the input gives the
output.
-
Here are 27 other examples, going back to quadratic functional equations
the input gives the
output.
Persoanl Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page