Re: m balls k urns

In article <1119134175.251003.194990@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
oercim <oercim@xxxxxxxxx> wrote:
> You are right. I think , I was wrong at the beginning. The
>urns shoud be distinguishable. So sorry. Then the right explanitation
>of the problem is
>
> 1. There are m indistinguishable balls and k distinguishable
>urns.
> 2. m>k
> 3. Each urn contains at least 1 ball
>
> So, how many different ways are there to put the balls into
>balls? Again sorry.

In this case, all you have to do is distribute m-k balls into k
distinguishable urns, with repetitions allowed. The problem was
already solved in another post, but here is a different way of solving
that problem, called "combinations with repetitions."


Suppose you want to choose r objects, out of s possibilities, with
repetitions allowed but in such a way that the order does not
matter. This is the same as counting how many different throws of r
dice, each with s faces, there are. We may as well assume the objects
are the numbers 1, 2, 3, ..., r.

Any possible choice can be described as a non-decreasing s-tuple.
For example, let's say we want to count how many different
throws of 3 dice with 6 sides each there are. Then we can list the
throws as a 3-tuple in which each number is less than or equal to the
next one:

(1,1,1), (1,1,2), (1,1,3), (3,5,6), (2,2,4), etc.

but we would not list (3,2,5) (instead, we would described that throw
as (2,3,5).

So take the r-tuple; then add 0 to the first coordinate, 1 to the
second coordinate, and 2 to the third coordinate. That is, if we want
to describe the throw with two 2's and a 5, we would start with
(2,2,5), and then add 0 to the first 2, 1 to the second, and 2 to the
5, to get the tuple (2, 3, 7).

It is easy to see that in doing this, we will end up with a 3-tuple of
numbers, chosen between 1 and 8 (= 6+(3-1)), with no repetitions. So
there are at most as many throws as there are ways of choosing 3
numbers from {1,2,3,4,5,6,7,8} without repetitions.

Conversely, say we have a choice of 3 numbers from {1,2,3,4,5,6,7,8}
without repetitions. Say.... 2, 5, 7. Then list them as an ordered
tuple, (2,5,7), and subtract 0 from the smallest, 1 from the second,
and 2 from the largest of the numbers. So instead of (2,5,7) we get
(2-0,5-1,7-2) = (2,4,5). Then we get a 3-tuple of numbers, all between
1 and 6, with possible repetitions, but which is nondecreasing; that
is, a possible throw of 3 dice. Thus, the number of possible throws is
at least the number of ways of choosing 3 numbers from
{1,2,3,4,5,6,7,8} without repetition. So in short, the number of
throws of 3 (indistinguishable) dice, with six (distinguishable) faces
each, is the same as C(8,3).

In general, with s choices out of {1,2,3,4,...,r}, we again list them
as an ordered s-tuple, add 0 to the first position, 1 to the second,
...., s-1 to the last, to get an ordered s-tuple of numbers between 1
and r+(s-1), with no repetitions. A similar argument to the above
tells you that the number of ways to choose s objects out of r
possibilities with repetitions allowed is the same as the number of
ways to choose s objects out of r+(s-1) possibilities, with NO
repetitions allowed, i.e., C(r+(s-1),s).


So: your problem reduces, after dropping one ball each into the k
urns, to the problem of distributing the remaining m-k balls into the
k urns. We can distinguish the urns, we cannot distinguish the balls,
and we can put more than one ball into the same urn. It's like
throwing m-k dice, each with k-faces, and then putting balls into the
urns according to the fall of the dice. That is, we are making m-k
choices out of k possibilities with repetitions allowed. According to
the analysis above, this is s=m-k, r=k, so the answer is

C(k+(m-k-1),m-k) = C(m-1,m-k)

It is also well known that C(a,b) = C(a,a-b) (since you can either
select the ones you want, or the ones you don't want). So

C(m-1,m-k) = C(m-1, (m-1)-(m-k)) = C(m-1,k-1)

thus the answer to your problem is C(m-1,k-1), as the book stated.

--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================

Arturo Magidin
magidin@xxxxxxxxxxxxxxxxx

.

Relevant Pages

  • Re: chess problem
    ... I'm not sure the urns formula will do it; I think it's a little more ... Now imagine all the cars in a row, ... make it impossible to park the SUV we need to place the s - c empty ... The urns are the c+1 slots between the cars, the balls are the s-c ...
    (sci.math)
  • Estimating correlations between groups using binomial sampling
    ... Consider a large number of urns containing balls of various colours. ... Looking at the raw data, I suspect that the numbers balls of different ... I might estimate the correlation ...
    (sci.stat.math)
  • Re: Placing Balls in Urns and Expected values
    ... urns, if balls are indexed, too. ... there are n possibilities how to place all balls into ... To compute probability, ... Any distinction vanishes. ...
    (sci.math)
  • Re: Help with Urn Problem
    ... number of SINGLY occuppied urns when M balls are randomly placed into N ... exactly one ball, and find the probability that exactly K, ... Herman Rubin, Department of Statistics, Purdue University ...
    (sci.stat.math)
  • Re: ..Simple (?) combinatorial problem?
    ... Any explanation would definitely be appreciated. ... place the final number of balls in the first two boxes; ... allowing repetitions but where order does not matter, ...
    (sci.math)