Two Combination Problems

Date: 06/04/99 at 15:03:11
From: jamie devlin
Subject: Probability

How many ways are there to distribute 40 identical items among 4 
people?

a) With each getting 10?
b) With each getting at least one?

I am not aware of any method of doing this problem.
Please help me.

Date: 06/04/99 at 18:01:55
From: Doctor Anthony
Subject: Re: Probability

>How many ways are there to distribute 40 identical items among 4 
>people?
>
>With each getting 10?

If the items are identical then there is only 1 way


>With each getting at least one?

You can model the situation as shown below, distributing *'s into 4 
containers.

     |****|********|****|****........**|     40 *'s in all.

If no container is empty then we cannot have two |'s next to each 
other, and we must start and end with a |. So there are three |'s to 
be placed at random into the 39 gaps between the 40 *'s. This can be 
done in C(39,3) = 9139 ways.

So we can distribute the identical objects in 9139 ways amongst the 4 
people so that each gets at least one object.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/   

Date: 06/05/99 at 11:11:39
From: jamie devlin
Subject: Probability

Given a collection of 2n objects, n identical and the other n 
distinct, how many different subcollections of n objects are there?

I have tried different solutions to this problem but I can't find the 
correct answer.

Date: 06/05/99 at 16:05:43
From: Doctor Anthony
Subject: Re: Probability

For any subcollection of n objects there will be another subcollection 
of n objects made up of those not chosen for the first. In effect we 
are dividing the total population into two groups each of size n.

In one of these groups we could have:

     0 distinct       n identical
     1     "          n-1   "
     2     "          n-2   "
    ...............................
     n-1   "           1    "
     n     "           0    "

So we could choose the distinct objects first and then top up with the 
necessary number of identical objects to give a total of n in the 
group.

We could choose 0 distinct objects from n in C(n,0) ways, we could 
choose 1 distinct object from n in C(n,1) ways and so on. So the 
number of ways of making up the group will be

   C(n,0) + C(n,1) + C(n,2) + ...... + C(n,n)

If you think of the binomial expansion of (1 + x)^n and then put x=1 
you will generate the series whose sum we require. So clearly the sum 
is given by

     (1 + 1)^n  = 2^n

However in generating these groups of size n we will have generated 
the complementary group also of size n, so our answer will be too 
large by a factor of 2.

   Number of ways of creating subcollections of size n = 2^n/2

                            = 2^(n-1)

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/