In mathematics, Catalan's problem asks the number of ways n + 1 factors can be completely parenthesized by n pairs of parentheses. For example, the following are the 14 ways that 5 factors can be parenthesized:
- (1 (2 (3 (4 5))))
- (1 (2 ((3 4) 5)))
- (1 ((2 3) (4 5)))
- (1 ((2 (3 4)) 5))
- (1 (((2 3) 4) 5))
- ((1 2) (3 (4 5)))
- ((1 2) ((3 4) 5))
- ((1 (2 3)) (4 5))
- ((1 (2 (3 4))) 5)
- ((1 ((2 3) 4)) 5)
- (((1 2) 3) (4 5))
- (((1 2) (3 4)) 5)
- (((1 (2 3)) 4) 5)
- ((((1 2) 3) 4) 5)
The numbers of ways of performing these pairings are the Catalan numbers.
Famous quotes containing the words catalan and/or problem:
“God forgives the sin of gluttony.”
—Catalan proverb, quoted in Colman Andrews, Catalan Cuisine.
“The family environment in which your children are growing up is different from that in which you grew up. The decisions our parents made and the strategies they used were developed in a different context from what we face today, even if the “content” of the problem is the same. It is a mistake to think that our own experience as children and adolescents will give us all we need to help our children. The rules of the game have changed.”
—Lawrence Kutner (20th century)