Distributing Objects

Date: 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/