help/catalan

   1 NAME
   2     catalan - Catalan number
   3
   4 SYNOPSIS
   5     catalan(n)
   6
   7 TYPES
   8     n           integer
   9
  10     return      integer
  11
  12 DESCRIPTION
  13     If n >= 0, this returns the Catalan number for index n:
  14
  15         catalan(n) = comb(2*n,n)/(n + 1)
  16
  17     Zero is returned for negative n.
  18
  19     The Catalan numbers occur in solutions of several elementary
  20     combinatorial problems, e.g. for n >= 1, catalan(n) is the number of
  21     ways of using parentheses to express a product of n + 1 letters in
  22     terms of binary products; it is the number of ways of dissecting a
  23     convex polygon with n + 2 sides into triangles by nonintersecting
  24     diagonals; it is the number of integer-component-incrementing paths
  25     from (x,y) = (0,0) to (x,y) = (n,n) for which always y <= x.
  26
  27 EXAMPLE
  28     > print catalan(2), catalan(3), catalan(4), catalan(20)
  29     2 5 14 6564120420
  30
  31 LIMITS
  32     none
  33
  34 LINK LIBRARY
  35     NUMBER *qcatalan(NUMBER *n)
  36
  37 SEE ALSO
  38     comb, fact, perm
  39