home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / math / 12896 < prev    next >
Encoding:
Internet Message Format  |  1992-10-08  |  1.1 KB
  1. Path: sparky!uunet!mcsun!sun4nl!tuegate.tue.nl!rw7.urc.tue.nl!wsadjw
  2. From: wsadjw@rw7.urc.tue.nl (Jan Willem Nienhuys)
  3. Newsgroups: sci.math
  4. Subject: Re: Catalan NUmbers
  5. Message-ID: <5879@tuegate.tue.nl>
  6. Date: 8 Oct 92 08:07:26 GMT
  7. References: <BvrFrn.53A@cs.columbia.edu>
  8. Sender: root@tuegate.tue.nl
  9. Reply-To: wsadjw@urc.tue.nl
  10. Organization: Eindhoven University of Technology, The Netherlands
  11. Lines: 19
  12.  
  13. In article <BvrFrn.53A@cs.columbia.edu> thanasis@cs.columbia.edu (Thanasis Tsantilas) writes:
  14. >
  15. >Is there a combinatorial ("bijective") way to prove that the 
  16. >Catalan numbers are equal to C(2n,n)/(n+1)? 
  17.  
  18. Yes there is.  The Catalan numbers are also equal to the
  19. number of grid paths in a square grid that connect two ends
  20. of a given diagonal without touching it anywhere except at the
  21. end points. 
  22.  
  23. The trick is called Andre's mirror trick of 1910.  First count all
  24. paths also those that touch the diagonal.  Then count the touchers,
  25. namely by reflecting the part from the start point to the first
  26. touch in the diagonal.  Presto!
  27.  
  28. Read about in Comtet's book on Advanced Combinatorics.
  29.  
  30. JWN
  31.  
  32.