home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / 9545 < prev    next >
Encoding:
Internet Message Format  |  1992-07-25  |  2.2 KB
  1. Path: sparky!uunet!mcsun!uknet!cam-cl!pavo.csi.cam.ac.uk!camcus!gjm11
  2. From: gjm11@cus.cam.ac.uk (G.J. McCaughan)
  3. Newsgroups: sci.math
  4. Subject: Re: Lattice points in a polytope? (How to find all of them?)
  5. Message-ID: <1992Jul25.145230.18897@infodev.cam.ac.uk>
  6. Date: 25 Jul 92 14:52:30 GMT
  7. References: <1992Jul24.132125.155015@ns1.cc.lehigh.edu>
  8. Sender: news@infodev.cam.ac.uk (USENET news)
  9. Organization: U of Cambridge, England
  10. Lines: 46
  11. Nntp-Posting-Host: bootes.cus.cam.ac.uk
  12.  
  13. In article <1992Jul24.132125.155015@ns1.cc.lehigh.edu>, fc03@ns1.cc.lehigh.edu (Frederick W. Chapman) writes:
  14.  
  15. >                   Let S be the simplex (the simplest example of a convex
  16. > polytope) defined by the inequalities
  17. > 
  18. >                        x_i >= 0 for i = 1, 2,..., n
  19. >                         x_1 + x_2 + ... + x_n <= M
  20. > 
  21. > where n is a positive integer, and M is a non-negative integer.  The number
  22. > of integer lattice points inside S is given by the binomial coefficient
  23. > 
  24. >                                 ( M+n )
  25. >                                 (     )
  26. >                                 (  n  )
  27. > 
  28. > which is an n-th degree polynomial in M.
  29. > 
  30. > ...........................................................................
  31. > 
  32. > Pardon my boyish exuberence, but I think this a nifty fact.  How does one
  33. > go about proving this -- by induction on M?
  34.  
  35. I'm sure you can prove it by induction on M, but I think there's a nice
  36. combinatorial proof, something like this:
  37.  
  38. What we are asking for is sequences of n non-negative numbers whose sum is
  39. most M. Equivalently, n *positive* numbers whose sum is at most M+n (write
  40. N instead of M+n from now on).
  41.  
  42. So, draw N dots in a row:
  43.  
  44.   .   .   .   .   .   .   .   .
  45.  
  46. and consider the spaces after the dots:
  47.  
  48.   . | . | . | . | . | . | . | . |
  49.  
  50. and observe that choosing n positive numbers adding up to at most N is
  51. the same thing as choosing n of those |s; then x_i is the number of dots
  52. between the i'th | and the one before, and the sum of the x_i is the number
  53. of dots left of the right-most |.
  54.  
  55. How many ways are there to choose n |s out of those N? Answer: "N choose n",
  56. which is the answer given.
  57.  
  58. I think this proof is even prettier than the result itself.
  59.