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:
“It’s better that it should make you sick than that you don’t eat it at all.”
—Catalan proverb, quoted in Colman Andrews, Catalan Cuisine.
“I don’t have any problem with a reporter or a news person who says the President is uninformed on this issue or that issue. I don’t think any of us would challenge that. I do have a problem with the singular focus on this, as if that’s the only standard by which we ought to judge a president. What we learned in the last administration was how little having an encyclopedic grasp of all the facts has to do with governing.”
—David R. Gergen (b. 1942)