Fundamental Concepts of Mathematics

3. COMBINATORICS

3. Combinatorics In this chapter we are interested in counting the different ways in which a given event can occur. There is a great variety of such counting problems that we encounter in every day life and in mathematics. Here we shall discuss a few useful methods that can be applied to such problems. 3.1. BOXES AND BALLS We begin with a simple but typical problem. 3.1.1. Problem. There are two balls, one red and one blue, and three boxes numbered 1, 2 and 3. Find the number of ways in which the two balls can be put in the boxes, if each box can hold no more than one ball. Solution fa). With only two balls and three boxes the problem is easy enough to be solved experimentally. The six different ways are (Fig. 3.11: r--------I---------T--------, 1~~UI~U~IU~~l 11 2 3 11 2 3 11 2 3 I I I I I 1~~UI~U~IU~~1 I 1 2 3 I 1 2 3 I 1 ,2 3 I L ~ ~ L ~ Fig. 3.1 They are arranged in three groups of two placements each with the same box empty. _ In view of the fact that we shall be considering similar problems with far more balls and boxes, as well as variations of this problem in which some of the balls are not distinguishable from one another or the boxes 62 Fundamental Concepts of Mathematics have different capacities, we shall solve this problem by an alternative method wh ich can be appl ied to more compl icated situations. Solution (b). By an event we mean something that takes place or happens. Thus putting the two given balls into two of the three given boxes is an event, and we are interested in the number of distinct ways in which this event can occur. Let us denote this event by A and this number by w(A). We can also think of event A as a sequence of two events Band C: event B is to put the blue ball into one of the given boxes and event C is to put the red ball into one of the two boxes which remain empty after event B has taken place. Thus event A occurs whenever event B and event C occur together and vice versa. Let us count the occurrence of the events. Event B can occur in 3 distinct ways, and event C can occur in 2 distinct ways after event B has occurred. Therefore w(A) = w(B) w(C) =3 x 2 = 6. • In the very last step of the above solution (b) we have used a rather selfevident rule on the simultaneous occurrence of two events. Since we shall be making use of this rule frequently in our discussion, we formulate it as: 3.1.2. Rule of product. If one event can occur in m ways and another event can occur in n ways, then there are rn x n ways in which these two events can occur together. Using the method of solution (b), we can handle with ease any similar problem, with any number n ~ 2 of distinct boxes: there are altogether n(n - 1) ways to place two distinctly coloured balls in n distinctly numbered boxes. Suppose we now have r distinguishable balls and n distinguishable boxes, where r ~ n. Then there are n ways to place the first ball in the n boxes, n - 1 ways to place the second ball in the n - 1 remaining empty boxes, n - 2 ways to place the third ball in the now n - 2 remaining empty boxes, and so forth. Applying the rule of product r - 1 times, we obtain: 3.1.3. Theorem. The total number of distinct ways to put r distinguishable balls in n(n ~ r) distinguishable boxes is n! n (n - 1) (n - 2) . . . (n - r + 1) =(n _ r)! . Combinatorics 63 It is clear that with appropriate interpretation of the balls and boxes, Theorem 3.1.3 is adoptable to a great variety of problems of everyday life. 3.1.4. Example. A football team of 17 members is given 19 single rooms in a hostel. In how many ways can the members of the team be assigned to their rooms? Solution. We can take the members of the team as balls and the rooms as boxes...