home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / math / 12881 < prev    next >
Encoding:
Text File  |  1992-10-07  |  2.3 KB  |  44 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!stanford.edu!CSD-NewsHost.Stanford.EDU!Sunburn.Stanford.EDU!pratt
  3. From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
  4. Subject: Re: Catalan NUmbers
  5. Message-ID: <1992Oct8.024654.20141@CSD-NewsHost.Stanford.EDU>
  6. Sender: news@CSD-NewsHost.Stanford.EDU
  7. Organization: Computer Science Department,  Stanford University.
  8. References: <BvrFrn.53A@cs.columbia.edu> <BvrvJJ.HqG@cs.psu.edu>
  9. Date: Thu, 8 Oct 1992 02:46:54 GMT
  10. Lines: 32
  11.  
  12. In article <BvrvJJ.HqG@cs.psu.edu> plu@math.psu.edu (Todd Andrew Simpson) writes:
  13. >This is described in Knuth's book, The Art of Computer Programming,
  14. >Volume I (which is where I found it).  Another approach might be to
  15. >associate each of a set of C_n objects (there are lots of sets
  16. >enumerated by the C_n) with paths from (0,0) to (n,n) in such a way
  17. >that there are n+1 paths for each of the objects.  I haven't seen such
  18. >a proof, though it'd be interesting since one would not need to know
  19. >_a priori_ that C(2n,n)/(n+1) was equal to C(2n,n)-C(2n,n-1).
  20.  
  21. Well, I don't know whether C(2n,n)/(n+1) = (2n)!/(n!(n+1)!) =
  22. C(2n+1,n)/(2n+1) is any simpler than the algebra you wanted to avoid,
  23. but let's pretend it is.  Now consider the C(2n+1,n) paths from (0,0)
  24. to (n+1,n), aka that many strings of n+1 X's and n Y's.  Now all 2n+1
  25. rotations (cyclic shifts) of any such string must yield 2n+1 distinct
  26. strings, otherwise one of the 2n intermediate points along the
  27. corresponding path from (0,0) to (n+1,n) would have to lie on the
  28. diagonal (the straight line from (0,0) to (n+1,n)), impossible since
  29. only the endpoints of this diagonal lie on lattice points.  It can be
  30. seen that exactly one of the 2n+1 paths corresponding to these
  31. rotations does not contain any point lying strictly above the
  32. diagonal.  The string corresponding to that path must start with an X;
  33. delete that X to yield a balanced string (every prefix has at least as
  34. many X's as Y's).  Conversely, prefixing a balanced string with an X
  35. yields such a path.
  36.  
  37. (Heard this one from Knuth around 1971.  I don't see it in Vol. I and
  38. I can't remember where it's written down.)
  39.  
  40. -- 
  41. =================================================== In short, I am floundering
  42. Vaughan Pratt   pratt@cs.Stanford.EDU  415-494-2545 around and don't take what
  43. =================================================== I say seriously.
  44.