Illinois State University Mathematics Department

 MAT 305: Combinatorics Topics for K-8 Teachers

### Arranging Elements When Repetition Is Allowed

Here we pose two questions to help illustrate the problems we will explore as we enter Chapter 3. Here's the first question:

How many different birth-order arrangements are possible for a couple whose seven children consist of three sons and four daughters? Do not consider multiple births such as twins or triplets.

Let us use the symbols S S S and D D D D to represent the three sons and four daughters. Note that we are not concerned with the fact that indeed the three sons are different individuals, but only with their characterization as a male child in the family. Likewise with the four daughters.

We need to consider all possible ways to arrange the seven symbols. For instance, they could be arranged as SDSDDSD or as DSSSDDD. To enumerate all possibilities may take some time.

One way to systematically approach the problem is to think of the 7 birth-order positions as slots to be filled with the 7 symbols SSSDDDD: _ _ _ _ _ _ _. In placing the three sons in these slots, we have to select 3 of the 7 positions. If we select the first, fourth, and seventh positions, for instance, we have no concern about which S goes in each slot. The set {S,S,S} contains three identical elements.

Thus, we have a combination situation, selecting 3 from 7 and disregarding the arrangement of the 3 items in the three selected spots. This is just C(7,3) = 35 possibilities.

Curiously, note that when we apply the same reasoning to the selection of 4 of the 7 positions for the daughters, we generate the same result, for C(7,4) = 35 possible selections of 4 positions from 7 available slots. Will this always be true?

Consider what may appear to be an apparently unrelated problem:

In a 9-by-6 rectangular grid that represents city streets (see figure: 9 rows and 6 columns, or 9 blocks high by 6 blocks wide), how many different paths exist that move from one vertex (extreme corner) of the grid to the vertex (extreme corner) diagonally opposite the first? We limit ourselves to paths of length 15 units, or, alternatively, we say that when a path begins, each subsequent move on the path must bring us closer to our target.

Regardless of the particular path we travel on the 9-by-6 grid, we must move 6 units across and 9 units up (or down). In terms of map directions, if we begin in the southwest corner of the grid, our path must travel a total of 6 blocks east and 9 blocks north.

Here lies the similarity to the birth-order arrangement problem just discussed. We have 15 "moves" in any one path, and that must include E E E E E E and N N N N N N N N N, where E represents one block moved in the easterly direction and N represents one block moved in the northerly direction. How many ways exist to arrange these 15 items, 6 of which are identical Es and 9 of which are identical Ns?

Concentrating on the Es, we have C(15,6) = 15!/(9!6!). Concentrating on the Ns, we have C(15,9) = 15!/(6!9!). Regardless of which perspective we take, the result is the same.

So, is our solution to this problem C(15,6) or is it C(15,6)*C(15,9)?

Here is a second question to help explore a generalization of the birth-order problem. Here, we look at the arrangement of more than two different elements, again with possible repetition of the elements:

How many ways are there to place 18 donuts on a tray to form a single line if we have 4 identical jelly-filled donuts, 6 identical sugar donuts, and 8 identical chocolate donuts?

Symbolize the donuts using J J J J, S S S S S S, and C C C C C C C C.

Imagine 18 boxes in a row, one for each donut. First, place the Js. There are 18 boxes from which we must select 4. Note again that the order of this selection is unimportant, because the 4 Js are identical. Thus, we have C(18,4) ways to select the positions for the Js.

There remain 14 boxes for the six Ss. The boxes for the Ss can be selected in C(14,6) ways.

In reality, we are done. But let us continue the pattern: There are 8 Cs to be placed in 8 boxes. Because the Cs are identical, there is only one way to complete the task. It is helpful, however, to look at combinatorial symbolism to represent this: C(8,8).

Thus, we have C(18,4), C(14,6), and C(8,8). What do we do with these values? Because each of the C(14,6) ways to place the Ss can be matched with each of the C(18,4) ways to place the Js, and so on, we use the multiplication principle: C(18,4)*C(14,6)*C(8,8).

Take a look at how this simplifies using factorial notation: Could we have proceeded in a different order and generated the same result?

Does this agree with what we determined in the birth-order selection problem? Check that result using the reasoning applied to the donut problem:

There are C(7,3) ways to select positions for the Ss. This leaves C(4,4) ways to select positions for the Ds. By multiplication we get It seems that there is a pattern in the numerator and denominator of our result, in terms of the total number of positions to be fills and the number of each item available for filling those positions. If we have 30 positions to fill and there are 7 identical items of a first kind, 3 identical items of a second kind, 11 identical items of a third kind, 5 identical items of a fourth kind, and 4 identical items of a fifth kind, our investigation suggests that there are ways to make our selection.

Let us generalize this suggestion.

 Arrangement of Elements with Repetition We can use combinatorial reasoning to justify our result, just as we did in the specific case where k = 3 different types of donuts. That is, there are ways to select the positions. In factorial notation, this is which simplifies to 