Two Combination ProblemsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/