Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/