Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Math Forum
»
Discussions
»
sci.math.*
»
sci.stat.math
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
Generation of random binary trees
Replies:
10
Last Post:
Mar 20, 2014 10:30 AM




Re: Generation of random binary trees
Posted:
Mar 2, 2014 4:09 AM


Am 02.03.2014 00:54, schrieb Joe keane: > In article <lelj4l$2s7$1@news.albasani.net>, > MokKong Shen <mokkong.shen@tonline.de> wrote: >> Given n, I want to randomly generate a binary tree (unlabelled) that >> has n end nodes. Could someone kindly provide a reference containing >> an algorithm for doing that? > > They are counted by Catalan numbers. > > At worst you can generate some random strings like "()(())" and throw > out the ones that are illegal. > > There's probably a better way.
Isn't it that the Catalan number gives only the total count. Given a number less the total count, how could one determine the corresponding tree algorithmically?
M. K. Shen



