Associated Topics || Dr. Math Home || Search Dr. Math

### 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.
```

```
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
```

```
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/
```
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