Catalan's problem

In mathematics, Catalan's problem asks the number of ways "n" factors can be completely parenthesized by "n" − 1 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.

ee also

*Catalan number
*Eugène Charles Catalan

References

*cite book
last = Gardner
first = Martin
authorlink = Martin Gardner
coauthors =
title = Time Travel and Other Mathematical Bewilderments
publisher = W.H. Freeman and Company
date = 1988
location = New York
pages = p. 256
url =
doi =
id =
isbn = 0-7167-1924-X
*MathWorld|title=Catalan's Problem|urlname=CatalansProblem