Where do Catalan numbers occur?
-Number of psp with a given number of pairs of brackets
-Number of binary trees with given number of leaves
-The number of paths from the lower left corner to the upper right corner in the square n * n that do not touch the diagonal
-Number of divisions of the n-gon into triangles
How to count?1) Formula for the nth Catalan number:
2)
•Let's have a PSS of length 2n
•Obviously it starts with an opening brace
•So, say P = (A)B, where A and B – also psp (moreover, A and B can be empty)
•If the length of A = 2k, then the sequence A can be composed in Ck ways
•Then the length of B = 2(n – k - 1) and B can be composed in Cn-k-1 ways
•We see the formula for dp: Cn = sum(Ck * Cn-k-1) for all k <
Materials used: