CHAPTER 8 - More Applications

By now, you should have a pretty good idea about the basics of permutations and combinations. In this section, we will encounter more advanced problems.

All the questions discussed in the following pages are directly or indirectly based on the concepts already discussed in the previous sections. In case you find anything confusing, refer to the relevant parts again.

Example: 1

On a standard  chessboard, find the (a) number of rectangles (b) number of squares

Solution: 1-(a)

Visualise any arbitrary rectangle on the chessboard, say the one depicted on the left in the figure below: As explained in the figure above, any rectangle that we select can be uniquely determined by specifying the pair of lines  and  that make up the vertical edges of the rectangle and the pair of lines  and  that make up the horizontal edges of the rectangle. On the chessboard, there are  vertical lines available to us from which we have to select . This can be done in  ways. Similarly,  horizontal lines can be selected in  ways. Thus, the total number of rectangles that can be formed is .

Solution: 1-(b)

To select a square, observe that the pair of lines  and  must have the same spacing within  and  as the pair of lines  and . Only then can the horizontal and vertical edges of the selected rectangle be of equal length (and thus, the selected rectangle is actually a square). In how many ways can we select a pair  of lines which are spaced a unit distance apart ? Its obviously . Corresponding to each of these  pairs, we can select a pair  of lines in  ways such that  and  are a unit distance apart. Thus, the total number of unit squares is  (This is obvious otherwise also). Now we count the number of  squares. In how many ways can we select a pair  of lines which are  units apart ? A little thought shows that it will be . Corresponding to each of these pairs, we can select a pair  of lines in  ways such that  and  are units apart. Thus, the total number of  squares is . Reasoning this way, we find that the total number of  squares will be , the total number of  squares will be  and so on. Thus, the total number of all possible squares is

Example: 2

Consider an -sided convex polygon. (a) In how many ways can a quadrilateral be formed by joining the vertices of the polygon ? (b) How many diagonals can be formed in the polygon?

Solution: 2-(a)

Observe that a selection of any  points out of the  vertices of the quadrilateral will give rise to a unique quadrilateral (since the polygon is convex, the problem of our selection containing all or  collinear points does not exist).  points out of  can be selected in  ways. Thus, we can have  different quadrilaterals.

Solution: 2-(b)

To form a diagonal, we need  non-adjacent vertices ( because  adjacent vertices will form a side of the polygon and not a diagonal). The total number of ways of selecting  vertices out if  is . This number also contains the selections where the  vertices are adjacent. Those selections are simply  in number because the polygon has  sides. Thus, the total number of diagonals is