Mike, Today I thought about what you wrote, but I can't work out the correspondance between the binary trees and your characterization of them, and your equation(s) that are solved to get the generating function. You use "leaf" to describe a null tree, which is okay, but the series given by your solution makes Catalan[0]=0, rather than 1, and the rest are all off by one as well. To get the true Catalan numbers (and avoid using "leaf" which sometimes describes a terminal node), I would suggest defining a tree this way: "A tree is either the null tree, or it is a node with two children (either of which could be the null tree)" Which produces an equation more like yours, and agreeing with the derivation at [1]: T(x) = 1 + x*T(x)^2 The 1 represents the null tree, because it is the coefficient of x^0. The normalized polynomial is: x*T(x)^2 - T(x) + 1 = 0 Solving for T(x) (with the quadratic formula treating T(x) as the variable): T(x) = [1 +- sqrt(1 - 4*x)] / 2x Putting "Series[(1-sqrt(1-4*x))/(2*x),{x,0,7}]" into Wolfram Alpha [2] gives the proper Catalan series 1+x+2x^2+5x^3+... Plugging in 1/1000 for x, we get 1000*(1-sqrt(1-4/1000))/2 = 1.001002005014... which puts the initial "1" in the proper place. Returning finally to the original topic of this thread, this is much easier to remember in the form: 500-sqrt(500^2-500*2) = 1.001002005014... - Robert [1] http://en.wikipedia.org/wiki/Catalan_number#First_proof [2] http://www.wolframalpha.com/input/?i=Series%5B%281-sqrt%281-4*x%29%29%2F%282*x%29%2C{x%2C0%2C7}%5D P.S. In all cases the quadratic formula gives two solutions. I don't know the tree interpretation of the series you get from "Series[(1+sqrt(1-4*x))/(2*x),{x,0,7}]" which has "negative Catalan numbers" in most of its terms. Also, I worked out the series for counting non-null binary trees, based on interpreting "leaf" as "terminal node" or "node with no children", which is the more normal use of the term "leaf" in e.g. computer data structures. The verbal description becomes: "A tree is either a node with no children, or a node with a tree as its left child, or a node with a tree as its right child, or a node with two trees as children." Using A(x) for the series, the equation is: A(x)=x+x*A(x)+x*A(x)+x*A(x)^2 which solves to: A(x)=[1-2*x+-sqrt(1-4*x)]/(2*x) Putting "Series[(1-2*x-sqrt(1-4*x))/(2*x),{x,0,7}]" into Wolfram Alpha indeed gives the Catalan series with the initial 1 term missing. On Fri, Feb 3, 2012 at 10:17, Mike Stay <metaweta@gmail.com> wrote:
What I find easiest to remember is the generating function for binary trees. A tree is either a node with a pair of trees as children, or a leaf. So T(x) = T(x)^2 + x or T(x)^2 - T(x) + x = 0
T(x) = [1 +/- sqrt(1 - 4x)]/2
If we plug in 1/1000, we get [1+/-sqrt(1-4/1000)]/2 = 0.001001002005014
On Thu, Feb 2, 2012 at 11:46 PM, Robert Munafo <mrob27@gmail.com> wrote:
Yesterday I found the far easier-to-remember:
500 - sqrt(499*501)
which also has secondary advantages of giving you 6 digits for each Catalan number, and being far easier to expand to an 8-digit or longer version if you want.
- Robert
mrob.com/pub/math/seq-digits.html#irrational
On Sun, Jan 29, 2012 at 10:39, Warren Smith <warren.wds@gmail.com> wrote:
Jorg Arndt's example generating Pascal's triangle and a Fibonacci-like sequence was considerably cooler... another I invented quite a while back was
1000 / (500 + sqrt(249990)) = 1.00001000020000500014000420013200429014300...
where the sequence 1,2,5,14,42,... is the Catalan numbers (which easily give you the central binomial coefficients).
How did I do that? Well, again, one way is using generating functions.
But the continued fraction of quadratic irrationals is ultimately periodic and once you know its period you can easily solve for the surd, so again, this is easy to construct from the desired sequence without any intelligence.
-- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com