Arrangements of non-distinct objects

First let’s use a simple example to review the two basic counting rules that we have discussed. Suppose you are making up silly words from the letters "a", "b", "c", "d", "e", "f", like

bacedf, decabf, eabcfd

How many silly words can I make up? Here we have n = 6 objects, and so the number of possible permutations is

$6!=6\times5\times4\times3\times2\times1=720$

To illustrate the second counting rule, suppose I have six letters "a", "b", "c", "d", "e", "f", and I am going to choose three of the letters to construct a three-letter word. I can't choose the same letter twice and the order in which I choose the letters is not important. In this case, we are interested in the number of combinations -- applying our combination rule with n = 6 and k = 3, the number of ways of choosing three letters from six is equal to

$_6C_3=\frac{6!}{3!3!}=20$

Let's consider a different arrangement problem. Suppose we randomly arrange the four triangles and five squares as shown below.

P3.clip9.png

What is the chance that the first and last locations are occupied by triangles? This is an arrangement problem with one difference -- the objects are not all distinct -- we can't distinguish the four triangles or the five squares. So we can't use our earlier permutation rule that assumes the objects are distinguishable.

How can we count the number of possible arrangements? It turns out that a combination formula is useful here. (Surprising, but true.)

To think about possible arrangements, suppose we write down a list of nine slots and an arrangement is constructed by placing the triangles and the squares in the nine slots. It is helpful to label the slots with the numbers 1 through 9.

P3.clip10.png

We construct an arrangement in two steps. First, we place the four triangles in four slots, and then we place the squares in the remaining slots.

How many ways can we put the triangles in the slots? First note that we can specify a placement by the numbers of the slots that are used. For example, we could place the triangles in slots 1, 3, 4, and 8.

P3.clip11.png

Or we could place the four triangles in slots 2, 5, 7, and 8.

P3.clip12.png

We can specify an arrangement by choosing four locations from the slot locations {1, 2, 3, 4, 5, 6, 7, 8, 9}. How many ways can we do this? That's easy. We know that the number of ways of selecting four objects (here labels of locations) from a group of nine objects is

$_9C_4=\frac{9!}{4!\left(9-4\right)!}=126$

So there are 126 ways of choosing the four locations for the triangles. Once we have placed the triangles, we can finish the arrangement by putting in the squares. But there is only one way of doing this. For example, if we place triangles in slots 2, 5, 6, 7, then the squares must go in slots 1, 3, 4, 8, 9. So applying the multiplication rule, the number of ways of arranging four triangles and five squares is 126 x 1 = 126.

We have derived a new counting rule:

PERMUTATIONS RULE FOR NON-DISTINCT OBJECTS: The number of permutations of n non-distinct objects where r are of one type and n - r are of a second type is

$_nC_r=\frac{n!}{r!\left(n-r\right)!}$

Recall our question that we wanted to answer: Suppose we randomly arrange four triangles and five squares. What is the chance that the first and last locations are occupied by triangles?

We have already shown that there are 126 ways of mixing up four triangles and five squares. Each possible arrangement is equally likely and has a chance of 1/126 of occurring.

To find our probability, we need to count the number of ways of arranging the triangles and squares so that the first and last positions are filled with triangles.

P3.clip13.png

If we place triangles in slots 1 and 9 (and there is only one way of doing that), then we are free to arrange the remaining two triangles and five squares in slots 2, 3, 4, 5, 6, 7, 8, 9. By use of our new arrangements formula, the number of ways of doing this is

and so our probability the first and last slots are filled with triangles is equal to 21/126.