home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / sci / math / 17475 < prev    next >
Encoding:
Text File  |  1992-12-29  |  1.4 KB  |  46 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!uwm.edu!linac!att!cbnews!cbnewsm!thf
  3. From: thf@cbnewsm.cb.att.com (thomas.h.foregger)
  4. Subject: Re: Combinatorial? problem
  5. Organization: AT&T
  6. Date: Tue, 29 Dec 1992 04:19:21 GMT
  7. Message-ID: <1992Dec29.041921.29638@cbnewsm.cb.att.com>
  8. Summary: soln of the problem
  9. References: <Dec.23.18.15.49.1992.22657@pepper.rutgers.edu>
  10. Keywords: binomial coefficients
  11. Lines: 33
  12.  
  13. In article <Dec.23.18.15.49.1992.22657@pepper.rutgers.edu>, gore@pepper.rutgers.edu (Bittu) writes:
  14. > 
  15. > Someone please help me with the following problem. I have pretty much
  16. > given up on it after a lot of thinking. We want to show the following:
  17. > 
  18. > given m,n nonnegative integers, the quantity
  19. > 
  20. >      (2m)! (2n)!
  21. >     -------------      is an integer.
  22. >      m! n! (m+n)!
  23. > 
  24. > 
  25. > Note that this is very easy to show by the standard argument where for
  26. > every prime p, you find the highest power of p (say p^k) that divides
  27. > the denominator and then show that p^k divides the numerator as well.
  28. > 
  29. > I want a combinatorial proof of this. I have tried rewriting the above
  30. > as C(2m,m)*C(2n,n)/C(m+n,m) where C(a,b) is "a choose b" and also in
  31. > other ways, but I still haven't come up with a combinatorial proof.
  32. > 
  33. > --Bittu
  34.  
  35.  
  36. Without loss of generality assume m<=n so m+n <= 2m.
  37. Write the ratio as
  38.  
  39. (2m)! . n! . (2n)!
  40. ----   ---   -----
  41. (m+n)!  m!   n! n!
  42.  
  43. Each of the 3 factors is clearly an integer, so the ratio is an integer.
  44.  
  45. tom foregger
  46.