home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / math / 17655 < prev    next >
Encoding:
Internet Message Format  |  1993-01-04  |  2.0 KB
  1. Path: sparky!uunet!spool.mu.edu!wupost!usc!news.service.uci.edu!beckman.com!dn66!a_rubin
  2. Newsgroups: sci.math
  3. Subject: Re: Combinatorial? problem
  4. Message-ID: <a_rubin.726176150@dn66>
  5. From: a_rubin@dsg4.dse.beckman.com (Arthur Rubin)
  6. Date: 4 Jan 93 19:35:50 GMT
  7. References: <Dec.23.18.15.49.1992.22657@pepper.rutgers.edu> <1992Dec29.041921.29638@cbnewsm.cb.att.com>
  8. Organization: Beckman Instruments, Inc.
  9. Keywords: binomial coefficients
  10. Nntp-Posting-Host: dn66.dse.beckman.com
  11. Lines: 40
  12.  
  13. In <1992Dec29.041921.29638@cbnewsm.cb.att.com> thf@cbnewsm.cb.att.com (thomas.h.foregger) writes:
  14.  
  15. >In article <Dec.23.18.15.49.1992.22657@pepper.rutgers.edu>, gore@pepper.rutgers.edu (Bittu) writes:
  16. >> 
  17. >> Someone please help me with the following problem. I have pretty much
  18. >> given up on it after a lot of thinking. We want to show the following:
  19. >> 
  20. >> given m,n nonnegative integers, the quantity
  21. >> 
  22. >>      (2m)! (2n)!
  23. >>     -------------      is an integer.
  24. >>      m! n! (m+n)!
  25. >> 
  26. >> 
  27. >> Note that this is very easy to show by the standard argument where for
  28. >> every prime p, you find the highest power of p (say p^k) that divides
  29. >> the denominator and then show that p^k divides the numerator as well.
  30. >> 
  31. >> I want a combinatorial proof of this. I have tried rewriting the above
  32. >> as C(2m,m)*C(2n,n)/C(m+n,m) where C(a,b) is "a choose b" and also in
  33. >> other ways, but I still haven't come up with a combinatorial proof.
  34. >> 
  35. >> --Bittu
  36.  
  37.  
  38. >Without loss of generality assume m<=n so m+n <= 2m.
  39. ???                                            >=
  40. >Write the ratio as
  41.  
  42. >(2m)! . n! . (2n)!
  43. >----   ---   -----
  44. >(m+n)!  m!   n! n!
  45.  
  46. >Each of the 3 factors is clearly an integer, so the ratio is an integer.
  47.  
  48. --
  49. Arthur L. Rubin: a_rubin@dsg4.dse.beckman.com (work) Beckman Instruments/Brea
  50. 216-5888@mcimail.com 70707.453@compuserve.com arthur@pnet01.cts.com (personal)
  51. My opinions are my own, and do not represent those of my employer.
  52. My interaction with our news system is unstable; please mail anything important.
  53.