Catalan Numbers and Catalan Convolution

Правка en1, от Dardy, 2021-02-07 15:58:28

Catalan Numbers is a well known sequence of integers that appear in combinatorics, there is a chance that you might have run into such counting problems and you might have even solved them with DP without realizing that they are a known sequence. Here are a few problems to get us started.

Find the count of different binary trees with $$$n$$$ nodes, we'll denote to that by $$$C_n$$$. This can be solved by observing the substructure of the problem:

binary tree

From the root, the left subtree $$$a$$$ can be any binary tree of length $$$x$$$, the right subtree $$$b$$$ can be any binary tree of length $$$y$$$, such that $$$x+y=n-1$$$. With the base case at $$$C_0=1$$$ as the empty tree is a valid tree of size $$$n$$$. This directly gives us the answer by the following recurrence relation: (Segner's recurrence relation) $$$C_{n+1} = \sum_{i=0}^{n}{C_i C_{n-i}}, n \geq 0; C_0=1$$$

The sequence of numbers $$$C_0, C_1, C_2, ...$$$ is called Catalan Numbers, and for reference they are: $$$1, 1, 2, 5, 14, 42, ...$$$

Теги #math, #catalan, #combinatorics

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский Dardy 2021-02-10 15:08:10 2
en7 Английский Dardy 2021-02-08 22:15:24 35 split formula into multiple lines
en6 Английский Dardy 2021-02-08 22:11:31 1293 UPD 1: added a not very detailed proof of the formula of catalan convolution
en5 Английский Dardy 2021-02-08 21:35:48 3195 (published)
en4 Английский Dardy 2021-02-08 14:00:21 254
en3 Английский Dardy 2021-02-08 05:19:00 4856
en2 Английский Dardy 2021-02-07 16:42:03 2035 Tiny change: 'es Count\n==================\nFind the' -> 'es Count\n------------------\nFind the'
en1 Английский Dardy 2021-02-07 15:58:28 1103 Initial revision (saved to drafts)