File Catalan.h

↰ Parent directory (ADS/numeric)

The numbers of Catalan, 1, 1, 2, 5, 14, 42, …: :math:` C_n ` counts the binary trees of n nodes (so the binary search trees on n keys, the trees whose symmetric visit is 1 .

Definition (ADS/numeric/Catalan.h)

Detailed Description

. n), the strings of n pairs of balanced parentheses, the full binary trees of n + 1 leaves (the parenthesizations of a product of n + 1 factors), the triangulations of a convex polygon of n + 2 sides, and the monotone lattice paths that never cross the diagonal.

catalan() fills the table of the recurrence on the size of the left subtree, :math:` C_0 = 1 ` and :math:` C_n = sum_{k=0}^{n-1} C_k C_{n-1-k} , with :math: Theta( n^2 ) ` operations on numbers of :math:` Theta( n ) ` bits, and with T = BigInteger for any n [see File BigInteger.h]. The closed form :math:` C_n = binom{2n}{n} / ( n + 1 ) ` and the recurrence :math:` C_{n+1} = 2 ( 2 n + 1 ) C_n / ( n + 2 ) ` take O( n ) operations, but their intermediate values exceed the result, so that in 64 bits they stop before the table does, which reaches :math:` C_{36} ; asymptotically :math: C_n sim 4^n / ( n^{3/2} sqrt{pi} ) `.

The contracts [see File Contract.h]: n >= 0, and :math:` C_n ` representable in T (n <= 36 for 64 bits unsigned). The functions are defined in Catalan.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, chapter 13, https://algoritmicamente.it/materiali/libro/capitoli/cap13.pdf

    1. Stanley, Catalan Numbers, Cambridge University Press, 2015, doi:10.1017/CBO9781139871495

    1. Knuth, The Art of Computer Programming, vol. 1, 3rd ed., Addison-Wesley, 1997, section 2.3.4.4

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions