Distributing ObjectsDate: 08/12/2001 at 14:09:14 From: ali khachan Subject: Probability-counting I need to know if there is a formula for distributing n indistinguishable objects into k indistinguishable urns. Date: 08/12/2001 at 16:06:38 From: Doctor Anthony Subject: Re: Probability-counting This is the same as partitioning a number n into exactly k parts, but the result will vary, depending on whether empty urns are permitted. You require the coefficient of x^n in the expansion of the generating function x^k ------------------------------- if empty urns not permitted (1-x)(1-x^2)(1-x^3).....(1-x^k) 1 or ------------------------------- if empty urns are permitted (1-x)(1-x^2)(1-x^3).....(1-x^k) To be of practical use you really need a mathematics package like Maple or Mathcad, and you can then get the result in a few seconds. Example: In how many ways can 15 balls be distributed into 6 urns with no urn empty? We require the coefficient of x^15 in the expansion of x^6 --------------------------------------- (1-x)(1-x^2)(1-x^3)(1-x^4)(1-x^5)(1-x^6) Maple gives the term 26.x^15 and so we know there will be 26 ways that we could distribute 15 balls into 6 indistinguishable urns. If empty urns are allowed, we require the coefficient of x^15 in the expansion of 1 --------------------------------------- (1-x)(1-x^2)(1-x^3)(1-x^4)(1-x^5)(1-x^6) In this case Maple gives the term 110.x^15 and so there will be 110 ways that 15 balls can be distributed into 6 urns with empty urns being permitted. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/