×

Towards a more precise analysis of an algorithm to generate binary trees: A tutorial. (English) Zbl 0927.11006

In connection with counting binary trees [see L. Xiang, C. Tang and K. Ushijima, Comput. J. 40, 278-291 (1997; Zbl 0885.68120)] the recursion \(g_{n,k}=g_{n-1,k-1}+2g_{n-1,k}+g_{n-1,k+1}+1\) occurred. In this note, the authors obtain an explicit formula and an explicit recursion for \(g_{n,0}\). They use these (rather complicated) formulae to obtain asymptotic results about \(g_{n,0}\). The proof uses the generating function of the sequence \((g_{n,0})\).

MSC:

11B37 Recurrences
05A15 Exact enumeration problems, generating functions
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science

Citations:

Zbl 0885.68120

Software:

gfun
PDFBibTeX XMLCite
Full Text: DOI Link