home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / 11023 < prev    next >
Encoding:
Text File  |  1992-09-07  |  2.3 KB  |  48 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!pipex!warwick!pavo.csi.cam.ac.uk!camcus!gjm11
  3. From: gjm11@cus.cam.ac.uk (G.J. McCaughan)
  4. Subject: Re: Permutation problem
  5. Message-ID: <1992Sep4.230042.23738@infodev.cam.ac.uk>
  6. Sender: news@infodev.cam.ac.uk (USENET news)
  7. Nntp-Posting-Host: bootes.cus.cam.ac.uk
  8. Organization: U of Cambridge, England
  9. References: <Bu14Ep.IEE@matilda.vut.edu.au>
  10. Date: Fri, 4 Sep 1992 23:00:42 GMT
  11. Lines: 35
  12.  
  13. In article <Bu14Ep.IEE@matilda.vut.edu.au>, kcj@matilda.vut.edu.au (Kate) writes:
  14.  
  15. > Can someone tell me the formula for getting the number
  16. > of permutations of any group of numbers that add up to a certain number. e.g.
  17. > how many permutations of length 5 add up to 20?
  18.  
  19. Erm, what is a "permutation" in this context? Do you mean: how many strings
  20. of numbers, no two of which are the same, add up to [whatever]?
  21.  
  22. If so...
  23.  
  24. These permutations come in "families" of size r! where r is the length of the
  25. strings (because rearranging a permutation leaves it a permutation and doesn't
  26. change what it adds up to). Dividing out by that, we want to know how many ways
  27. there are to chop 20 up into 5 different parts, where we aren't bothered about
  28. what order they come in.
  29.  
  30. This is the same as the number of ways to chop 10 = 20-(0+1+2+3+4) into 5 parts,
  31. where they needn't be different and we don't care what order they come in. (We
  32. can convert one type of "partition" into the other by subtracting 0 from the
  33. smallest part, 1 from the next-smallest, and so on.)
  34.  
  35. I don't think there's a terribly nice general formula. If you write p(n,r)
  36. for the number of ways to split n into r parts, where they don't have to be
  37. all different, then ... um ... either the smallest part is 1 [p(n-1,r-1) of
  38. these] or it's not and all the parts are at least 2 [p(n-r,r) of these].
  39. So p(n,r) = p(n-1,r-1) + p(n-r,r), and you can use this (plus trivial things
  40. about what happens when n or r is 0) to evaluate p(n,r) if n,r are small.
  41. There's probably a rather more efficient way for large n...
  42.  
  43. Certainly p(n) [the sum of all the p(n,r)] is not very well understood. There
  44. are recurrences, and estimates for large n, and a very few congruence relations;
  45. and there *is* a formula that calculates it, but it's Very Strange and has
  46. things like Bessel functions in it; but there's an awful lot that is not really
  47. understood at all.
  48.