Catalan's problem
Encyclopedia
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:
The numbers of ways of performing these pairings are the Catalan number
s.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, 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 number
Catalan number
In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involvingrecursively defined objects...
s.