home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / math / 17670 < prev    next >
Encoding:
Internet Message Format  |  1993-01-05  |  2.8 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!moe.ksu.ksu.edu!ux1.cso.uiuc.edu!roundup.crhc.uiuc.edu!focus!hougen
  2. From: hougen@focus.csl.uiuc.edu (Darrell Roy Hougen)
  3. Newsgroups: sci.math
  4. Subject: Re: Generalization of binomial theorem wanted
  5. Date: 5 Jan 1993 03:08:45 GMT
  6. Organization: Center for Reliable and High-Performance Computing, University of Illinois at Urbana-Champaign
  7. Lines: 55
  8. Message-ID: <1iau3tINNn3l@roundup.crhc.uiuc.edu>
  9. References: <1i8hqmINN1lf@roundup.crhc.uiuc.edu>
  10. NNTP-Posting-Host: focus.csl.uiuc.edu
  11. Keywords: binomial
  12.  
  13. hougen@focus.csl.uiuc.edu (Darrell Roy Hougen) writes:
  14.  
  15. % In terms of m and n, how many unique terms are there in
  16. %     (x_1 + x_2 + ... + x_m)^n
  17. % when it is expanded?
  18.  
  19. Thanks to everyone who reminded me about multinomial coefficients.  It
  20. should have been obvious.  I've included one response below:
  21.  
  22. # The number of terms equals the number of (a1,...,am) where each a is a
  23. # non-negative integer and a1+...+am = n. (Obviously.) Less obviously, this
  24. # number equals the binomial coefficient (m+n-1 choose m-1).
  25. # 
  26. # Why? Well, convert (a1,...,am) to a row of symbols like this: write down
  27. # a1 dots, then a slash, then a2 dots, then a slash, ..., then am dots. This
  28. # produces a row of m+n-1 symbols, of which m-1 are slashes and n are dots.
  29. # Conversely, given any such row we can get a sequence (a1,...,am) by counting
  30. # the number of dots between each pair of slashes (and at the start, and at
  31. # the end). So the number of (a1,...,am) equals the number of such rows of
  32. # symbols, and this is just (m+n-1 choose m-1) because we can choose m-1
  33. # "positions" to contain slashes and put dots in the other n.
  34. # 
  35. # The coefficient of x1^a1.x2^a2...xm^am, incidentally, is n!(a1!a2!...am!):
  36. # a so-called multinomial coefficient.
  37. # 
  38. # -- 
  39. # Gareth McCaughan     Dept. of Pure Mathematics & Mathematical Statistics,
  40. # gjm11@cus.cam.ac.uk  Cambridge University, England.    [Research student]
  41.  
  42.  
  43. I should have stated in the original post that I was looking for the
  44. number of terms in the complete polynomial of degree n by which I mean
  45. the polynomial with terms of all degrees less than or equal to n.
  46. This can easily be obtained from the multinomial coefficients by
  47. writing sum (i=1 to n) of (i+m-1 choose m-1).  This is equal to my
  48. original formula (and much simpler):
  49.  
  50. % The formula I have is
  51. %                 n 
  52. %             sum                 sum                 1  
  53. %             i = 1    k_1 <= k_2 <= ... <= k_i <= m
  54.  
  55. The second sum is just the multinomial coefficient.  This can be seen
  56. by noticing that there are still m-1 "slashes" and the number of
  57. "dots" between the (p-1)st pair of slashes can be computed by counting
  58. the number of k_j's corresponding the pth variable.  The number of
  59. k_j's is equal to 'i' which completes the proof.
  60.  
  61. Thanks again to all who responded.
  62.  
  63. Darrell R. Hougen
  64.  
  65.  
  66.  
  67.  
  68.