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

### Combinations with Duplicate Objects

```
Date: 06/22/99 at 13:02:10
From: Michael Black
Subject: Combinations: n_C_k when items are duplicated

We all know the combination formula for choosing k objects from n
items:

n!
n_C_k = -----------
k!(n - k)!

Here is what's confounding our group: What if some of the n items are
duplicated?

For instance, 6_C_3 from this list (ABBCCC). We know the value should
be lower than 6_C_3 = 20 (actually, it's 5), but can't figure out how
to modify the formula correctly.

Is it even appropriate to be using n_C_k for this problem?

```

```
Date: 06/22/99 at 16:55:28
From: Doctor Anthony
Subject: Re: Combinations: n_C_k when items are duplicated

This is a type of problem that is considerably more difficult than one
in which all objects are different. We require two bits of theory that
you may not have met before. The first concerns the number of ways of
distributing objects into distinct cells, and the second is the
inclusion-exclusion principle.

Suppose we have an equation of the form

x1 + x2 + x3 = 10

and we wish to find the number of integer solutions of this equation
with each of x1, x2, x3 having values that can range from 0 to 10.

We can model this problem by considering the number of ways that say
10 oranges could be distributed at random to 3 children (zero oranges
being allowed to one or two of the children).

We can illustrate the situation with * representing oranges and | |
representing a container. Thus

|*****|**|***| is a possible solution with x1 = 5,  x2 = 2,  x3 = 3

The number of solutions is the same as the number of ways we could
arrange 10 *'s and 2 |'s in every possible way.

12!
This is clearly seen to be  ------  =  C(12,10)
10! 2!

The two |'s represent the containers, and the number of | in any such
line-up is always 1 less than the number of containers.

So with r oranges and k children the result would be

(r+k-1)!
-----------  =  C(r+k-1,r)
r! (k-1)!

and similarly the number of solutions to the equation

x1 + x2 + x3 + ..... + xk = r   is simply  C(r+k-1,r)

So far so good, and this is okay provided there are no restrictions on
the x1, x2, values except that they must be less than r. When there
are restrictions on the individual x values then we must subtract from
C(r+k-1,r) the number of solutions where these x values are exceeded.
This is where the inclusion-exclusion principle comes in.

Inclusion-Exclusion Principle
------------------------------
It is easy to illustrate the principle with two or three probabilities
using a Venn diagram.

For example with two overlapping probabilities P(A) and P(B), we have

P(A or B) = P(A) + P(B) - P(A and B)

P(B), so to get it added once only we subtract it, giving rise to
the expression shown above.

With three overlapping probabilities P(A), P(B) and P(C) we get

P(A or B or C) = P(A) + P(B) + P(C)
- P(A and B) - P(B and C) - P(C and A)
+ P(A and B and C)

now the overlap of all 3 probabilities is added 3 times by the
first line of this equation, subtracted 3 times by the second line of
the equation and so must be added again by the third line.

The area corresponding to A and B BUT NOT C is added twice in the
first line and subtracted once in the second line, so it will appear
once as is required. Similarly for area B and C but not A, and the
area corresponding to C and A but not B, each will eventually appear
once only.

With more probabilities the pattern continues and the proof by
induction is not difficult but a little tedious. The name
'inclusion-exclusion' describes exactly what is happening. Regions are
being added a number of times and subtracted a number of times in such
a way that each region occurs exactly once.

The same ideas apply when we are talking about the NUMBER of elements
in a set. So

n(A or B or C) = n(A) + n(B) + n(C)
- n(A and B) - n(B and C) - n(C and A)
+ n(A and B and C)

and finally the number such that none of A, or B or C occur is

|~A and ~B and ~C| = |U| - n(A or B or C)

(where |U| is the universal set)

= |U| - SUM[n(A)] + SUM[n(A and B)] - n(A and B and C)

I shall now work through an example in which both of the above ideas
are put into action.

Determine the number of combinations of 10 letters that can be formed
from

3.A's,   4.B's,   5.C's

If there are no restrictions on any of the letters, this is simply our
10 oranges and 3 children problem again, and we saw there that the
number of possible solutions is C(12,10) = 66

This also corresponds to the universal set |U|

Let P1 be the property that a 10-combination has more than 3 A's
P2           "                   "             "       4 B's
P3           "                   "             "       5 C's

If Ai is the NUMBER of 10-combinations which have property Pi
(i=1,2,3)
Then

|~A and ~B and ~C| = 66 - SUM[A1] + SUM[A1 and A2] - A1 and A2 and A3

The set A1 consists of all 10-combinations in which A occurs 4 or more
times. If we take any one of these 10-combinations in A1 and remove 4
A's we are left with a 6-combination, so the number of unwanted
10-combinations in which P1 occurs is equal to the 6-combination
without a limit on the numbers of letters.

So |A1| = C(6+3-1,6) = C(8,6) = 28

and similarly  |A2| = C(7,5) = 21

|A3| = C(6,4) = 15

The set A1 and A2 consists of all 10-combinationsin which A occurs at
least 4 times and B occurs at least 5 times. If from any of these
10-combinations we remove 4 A's and 5 B's we are left with a
1-combination of the unrestricted set.

So         |A1 and A2| = C(1+3-1,1) = C(3,1) = 3

Similarly         |A2 and A3| = 0

and         |A3 and A1| = C(0+3-1,0) = C(2,0) = 1

also  |A1 and A2 and A3| = 0

Putting all these results together we get

|~A and ~B and ~C| = 66 - (28+21+15) + (3+0+1) - 0

=  6

So there are just 6 of the 10-combinations that can be chosen with the
restrictions on the numbers of letters.

This type of question is often very conveniently answered using
generating functions. To answer the problem that I worked through at
some length, the number of 10-combinations that can be made from
3 A's, 4 B's, 5 C's is found from the coefficient of x^10 in the
expansion of:

(1+x+x^2+x^3)(1+x+x^2+x^3+x^4)(1+x+x^2+x^3+x^4+x^5)

With the aid of Mathcad or some such computer assistance we get the
coefficient of x^10 is 6 in a few seconds. In effect the computer does
the thinking for you.

To get the coefficient of x^10 without computer assistance we can ease
the algebra a little by expressing the various brackets as sums of
geometric series.

1+x+x^2+x^3         = (1-x^4)/(1-x)

1+x+x^2+x^3+x^4     = (1-x^5)/(1-x)

1+x+x^2+x^3+x^4+x^5 = (1-x^6)/(1-x)

If we multiply these all together we get

(1-x^4)(1-x^5)(1-x^6)[1-x]^(-3)

[1-x^4 -x^5 -x^6 +x^9 +x^10 +x^11 -x^15]
[1+3x+6x^2+10x^3+15x^4+21x^5+28x^6+36x^7+45x^8+55x^9+66x^10+...

Picking out the coefficient of x^10 we get

66-28-21-15+3+1 = 6

3-combinations taken from  1 A, 2 B's, 3 C's.

The generating function is

(1+x)(1+x+x^2)(1+x+x^3) = 1 + 3x + 5x^2 + 6x^3 + 5x^4 + + 3x^5 + x^6

and since the coefficient of x^3 is 6 we know that there will be 6
combinations of 3 letters. This differs from the answer you quoted.

The actual combinations are

ABC, ABB, ACC, BBC, BCC, CCC

- 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