Question

Which of the following is not an application of Catalan Numbers?

(a) Counting the number of Dyck words

(b) Counting the number of expressions containing n pairs of parenthesis

(c) Counting the number of ways in which a convex polygon can be cut into triangles by connecting vertices with straight lines

(d) Creation of head and tail for a given number of tosses

The question was posed to me during a job interview.

I would like to ask this question from Catalan Number using Dynamic Programming topic in chapter Dynamic Programming of Data Structures & Algorithms II

Answer 1

Correct option is (d) Creation of head and tail for a given number of tosses

The best explanation: Counting the number of Dyck words, Counting the number of expressions containing n pairs of parenthesis, Counting the number of ways in which a convex polygon can be cut into triangles by connecting vertices with straight lines are the applications of Catalan numbers where as creation of head and tails for a given number of tosses is an application of Pascal’s triangle.