Chapter 3

Subsets and Arrangements

There are 25 students in the class. How many ways are there to choose 5 of them to form a committee? If among the chosen five, one is to be the chairperson, one the secretary and one the treasurer, in how many ways can this be arranged? In this chapter, our attention will be focused on the counting problems of the above types. We shall see how (MP) is used to solve such problems, and how (MP), by incorporating (AP), enables us to solve more complicated problems.

From now on, for each natural number n, we shall denote by the set of natural numbers from 1 to n inclusive, i.e.

Consider the 4-element set How many subsets of are there? This question can be answered readily by listing all the subsets of . Table 3.1 lists all the subsets according to the number of elements they possess: It is now easy to count the total number of subsets of

Table 3.1

We note that the 5 numbers, namely, 1, 4, 6, 4, 1 (whose sum is 16) shown in the rightmost column of Table 3.1 are the corresponding numbers of r-element subsets of , where r = 0,1,2,3,4. These numbers are very interesting, useful and important in mathematics, and mathematicians have introduced special symbols to denote them.

In general, given two integers n and r with we denote by the number of r-element subsets of . Thus, Table 3.1 tells us that

The symbol is read “n choose r”. Some other symbols for this quantity include

Now, what is the value of counts, by definition, the number of 2-element subsets of , we may list all these subsets as shown below:

and see that there are 10 in total. Thus, we have

You may ask: How about ? We are sure that we are too busy to have time to compute by listing all the 6-element subsets of . Thus, a natural question arises: Is there a more efficient way to compute ? The answer is “Yes”, and we are going to show you.

Let us first consider a different but related problem. How many ways are there to arrange any three elements of in a row? With a little patience, we can list all the required arrangements as shown in Table 3.2.

Table 3.2

Thus, there are 24 ways to do so. The answer is “correct” but the method is “naive”. Is there a cleverer way to get the answer?

Imagine that we wish to choose 3 numbers from and put them one by one into 3 spaces as shown.

This event can be thought of as a sequence of events: We first select a number from and place it in the 1st space; we then select another number and place it in the 2nd space; finally, we select another number and place it in the 3rd space. There are 4 choices for the first step, 3 choices (why?) for the second and 2 choices (why?) for the last. Thus, by (MP), there are 4·3·2 (=24) ways to do so. The answer agrees with what we obtained above. Isn’t this method better?

This method is better not only in shortening our solution, but also in giving us an idea on how to generalise the above result.

In the above example, we considered the number of ways of arranging 3 elements of in a row. We now ask a general question: Given integers r, n with how many ways are there to arrange any r elements of in a row?

Consider the r spaces shown in Figure 3.1.

Figure 3.1

We wish to choose r elements from {1,…, n} to fill the r spaces, where the ordering of elements matters. There are n choices for the 1st space. After fixing one in the 1st space, there are n – 1 choices remaining for the 2nd space. After fixing one in the 2nd space, there are n – 2 choices left for the 3rd space, and so on. After fixing one in the (r – 1)th space, there are n – (r – 1) choices left for the rth space. Thus, by (MP), the number of ways to arrange any r elements from in a row is given by

For convenience, let us call an arrangement of any r elements from in a row, an r-permutation of , and denote by the number of r-permutations of . Thus, we have

For instance, all the arrangements in Table 3.2 are 3-permutations of , and, by (3.1), the number of 3-permutations of is given by

which agrees with what we have counted in Table 3.2.

The expression (3.1) for Py looks a bit long. We shall make it more concise by introducing the following useful notation. Given a positive integer n, define n! to be the product of the n consecutive integers n, n – 1,…, 3,2,1; that is,

Thus 4! = 4 · 3 · 2 · 1 = 24. The symbol “n!” is read “n factorial”. By convention, we define 0! = 1.

Using the “factorial” notation, we now have

That is,

When n = 4 and r = 3, we obtain

which agrees with what we found before.

The expression (3.3) is valid when Consider two extreme cases: when r = 0 and r = n respectively. When r = 0, by (3.3),

(How can this be explained?) When r = n, an n-permutation of is simply called a permutation of . Thus, by (3.3) and that 0! = 1, the number of permutations of is given by

i.e.

Thus, for example, counts the number of permutations of , and we have, by (3.4),

Let us now return to the problem of evaluating the quantity .

We know from (3.3) that the number Py of r-permutations of is given by We shall now count this number (namely, the number of r-permutations of ) in a different way.

To get an r-permutation of , we may proceed in the following manner: first select an r-element subset of , and then arrange the chosen r elements in a row. The number of ways for the first step is, by definition, , while that for the second step is, by (3.4), r!. Thus, by (MP), we have

As

we have

and thus

For instance,

Note that when r = 0 or n, we have

Again, by convention, we define

By applying (3.5), one can show that the following identity holds (see Problem 3.1):

Thus,

We define as the number of r-permutations and as the number of r-element subsets of . Actually, in these definitions, can be replaced by any n-element set since it is the number of the elements but not the nature of the elements in the set that matters. That is, given any n-element set S, (respectively, ) is defined as the number of r-permutations (respectively, r-element subsets) of S. Any r-element subset of S is also called an r-combination of S.

We have introduced the notions of r-permutations (or permutations) and r-combinations (or combinations) of a set S. Always remember that these two notions are closely related but different. While a “combination” of S is just a subset of S (and thus the ordering of elements is immaterial), a “permutation” of S is an arrangement of certain elements of S (and thus the ordering of elements is important).

Exercise

3.1 Show that for non-negative integers r and n, with r ≤ n,

(i)

(ii)

(iii)

(iv)

3.2 Show that for 1 ≤ r ≤ n,

(i)

(ii)

(iii)

(iv)

(v)

3.3 Prove that the product of any n consecutive integers is divisible by n!.

3.4 Find the sum