home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / math / 12871 < prev    next >
Encoding:
Text File  |  1992-10-07  |  2.2 KB  |  53 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!wupost!uwm.edu!psuvax1!news
  3. From: plu@math.psu.edu (Todd Andrew Simpson)
  4. Subject: Re: Catalan NUmbers
  5. In-Reply-To: thanasis@cs.columbia.edu's message of Wed, 7 Oct 1992 16:42:59 GMT
  6. Message-ID: <BvrvJJ.HqG@cs.psu.edu>
  7. Sender: news@cs.psu.edu (Usenet)
  8. Nntp-Posting-Host: hilbert.math.psu.edu
  9. Organization: Department of Mathematics, Pennsylvania State University
  10. References: <BvrFrn.53A@cs.columbia.edu>
  11. Date: Wed, 7 Oct 1992 22:23:42 GMT
  12. Lines: 39
  13.  
  14. In article <BvrFrn.53A@cs.columbia.edu> thanasis@cs.columbia.edu (Thanasis Tsantilas) writes:
  15.  
  16.    Is there a combinatorial ("bijective") way to prove that the 
  17.    Catalan numbers are equal to C(2n,n)/(n+1)? 
  18.    The answer looks simple, so I thought there must be something.
  19.    I'm only aware of the generating function solution of the recurrence.
  20.    Any pointers to books/articles are appreciated.
  21.  
  22. There is a very elegant proof due to D. Andr\'e sometime in the 19th
  23. century: First, C(2n,n)/(n+1) = C(2n,n)-C(2n,n-1).  Then:
  24.  
  25.     The number of paths from (0,0) to (n,n) in the plane, with unit steps
  26. (1,0) and (0,1), is C(2n,n).
  27.  
  28.     The Catalan number C_n is the number of these paths that stay in the
  29. region {(x,y): y<=x}.
  30.  
  31.     The number of paths from (0,0) to (n+1,n-1) with unit steps (1,0) and
  32. (0,1) is C(2n,n-1).
  33.  
  34.     There is a bijection between paths (with unit steps (1,0) and (0,1))
  35. from (0,0) to (n+1,n-1) and those from (0,0) to (n,n) that do not stay in
  36. the region {(x,y): y<=x}: given the latter type of path, with the k-th
  37. step being the first to go into the region y>x, for i from 1 to k if the
  38. i-th step is (1,0) make it (0,1); if it is (0,1) make it (1,0).
  39.  
  40. This is described in Knuth's book, The Art of Computer Programming,
  41. Volume I (which is where I found it).  Another approach might be to
  42. associate each of a set of C_n objects (there are lots of sets
  43. enumerated by the C_n) with paths from (0,0) to (n,n) in such a way
  44. that there are n+1 paths for each of the objects.  I haven't seen such
  45. a proof, though it'd be interesting since one would not need to know
  46. _a priori_ that C(2n,n)/(n+1) was equal to C(2n,n)-C(2n,n-1).
  47.  
  48.    Thanasis Tsantilas
  49.    Columbia University
  50.    thanasis@cs.columbia.edu
  51.  
  52. - Todd Andrew Simpson
  53.