Catalan's Problem

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:

    The table kills more people than war does.
    Catalan proverb, quoted in Colman Andrews, Catalan Cuisine.

    It is commonplace that a problem stated is well on its way to solution, for statement of the nature of a problem signifies that the underlying quality is being transformed into determinate distinctions of terms and relations or has become an object of articulate thought.
    John Dewey (1859–1952)