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
Math Forum Home || Math Library || Quick Reference || Math Forum Search