# Permutations and Combinations Set 1

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 – 16 **

On a standard 8 × 8 chessboard, find the

**(a)** number of rectangles **(b)** number of squares

**Solution: (a)** Visualise any arbitrary rectangle on the chessboard, say the one depicted on the left in the figure below:

**Fig. 14**

As explained in the figure above, any rectangle that we select can be uniquely determined by specifying the pair of lines *X* and *Y* that make up the vertical edges of the rectangle and the pair of lines *P* and *Q* that make up the horizontal edges of the rectangle.

On the chessboard, there are 9 vertical lines available to us from which we have to select 2. This can be done in \({}^9{C_2}\) ways. Similarly, 2 horizontal lines can be selected in \({}^9{C_2}\) ways. Thus, the total number of rectangles that can be formed is \({}^9{C_2} \times {}^9{C_2} = 1296\) .

**(b)** To select a square, observe that the pair of lines *X* and *Y* must have the same spacing within *X* and *Y* as the pair of lines *P* and *Q*. 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 (*X*, *Y*) of lines which are spaced a unit distance apart ? Its obviously 8. Corresponding to each of these 8 pairs, we can select a pair (*P*, *Q*) of lines in 8 ways such that *P* and *Q* are a unit distance apart. Thus, the total number of unit squares is 8 × 8 = 64 (This is obvious otherwise also). Now we count the number of 2 × 2 squares. In how many ways can we select a pair (*X*, *Y*) of lines which are 2 units apart ? A little thought shows that it will be 7. Corresponding to each of these 7 pairs, we can select a pair (*P*, *Q*) of lines in 7 ways such that * P* and *Q* are 2 units apart. Thus, the total number of 2 × 2 squares is 7 × 7 = 49.

Reasoning this way, we find that the total number of 3 × 3 squares will be 6 × 6 = 36, the total number of 4 × 4 squares will be 5 × 5 = 25 and so on.

Thus, the total number of all possible squares is

\[\mathop {64}\limits_{\scriptstyle\,\,\,\,\,\,\,\,\,\,\,\, \uparrow \atop \scriptstyle\,1 \times 1\,\,{\rm{squares}}} + \mathop {49}\limits_{\scriptstyle\,\,\,\,\,\,\, \uparrow \atop{\scriptstyle\,\,\,\,2 \times 2\atop\scriptstyle{\rm{squares}}}} + \mathop {36}\limits_{\scriptstyle\,\,\,\,\,\, \uparrow \atop {\scriptstyle\,\,\,3 \times 3\atop \scriptstyle{\rm{squares}}}} + ........... + \mathop 4\limits_{\scriptstyle\,\,\,\,\,\,\, \uparrow \atop{\scriptstyle\,\,\,\,7 \times 7\atop\scriptstyle{\rm{squares}}}} + \mathop 1\limits_{\scriptstyle\,\,\,\,\,\,\, \uparrow \atop{\scriptstyle\,\,\,\,8 \times 8\atop\scriptstyle{\rm{squares}}}} = 204\]

**Example – 17 **

Consider an *n*-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:** **(a)** Observe that a selection of any 4 points out of the *n* vertices of the quadrilateral will give rise to a unique quadrilateral (since the polygon is convex, the problem of our selection containing all or 3 collinear points does not exist). 4 points out of *n* can be selected in \({}^n{C_4}\) ways. Thus, we can have \({}^n{C_4}\) different quadrilaterals.

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

\[\begin{align}&\;\;{}^n{C_2} - n\\&= \frac{{n(n - 1)}}{2} - n\\ &= \frac{{n(n - 3)}}{2}\end{align}\]

**Example – 18 **

Give a combinatorial (logical) justification for this assertion:

\[{}^n{C_0} + {}^{n + 1}{C_1} + {}^{n + 2}{C_2} + ... + {}^{n + r}{C_r} = {}^{n + r + 1}{C_r}\]

**Solution: ** The right hand side tells us that we have to select *r* persons out of a group of \(n + r + 1\) persons. To do so, we consider any particular group of *r* persons from these \(n + r + 1\) persons. Specify these *r* persons by the symbols \({A_1},{A_2}...{A_r}\) .

Now, to count all the possible *r*-groups from this group of \(n + r + 1\) , we consider the following mutually exclusive cases:

**(1)The r -group does not contain \({A_1}\) **

Such *r*-groups can be formed in \({}^{n + r}{C_r}\) ways since we have to select *r* people out of *n *+ *r.*

**(2)** **The r -group contains ** \({A_1}\)

**but not**\({A_2}\)

We have to select (*r* – 1) people out of \((n + r - 1)\) because we already have selected \({A_1}\) so we need only *r* –1 more people and since we are not taking \({A_2}\) ,we have \((n + r - 1)\) people to choose from. This can be done \({\,^{n + r - 1}}{C_{r - 1}}\) ways.

**(3)** **The r -group contains ** \({A_1},{A_2}\)

**but not**\({A_3}\)

We now have to select (*r* – 2) people out of \((n + r - 2)\) . This can happen in \({}^{n + r - 2}{C_{r - 2}}\) ways. Proceeding in this way, we arrive at the last two possible cases.

**( r)**

**The**

*r*-group contains \({A_1},\,\,{A_2}...{A_{r - 1}}\) but not \({A_r}\) .We need to select only 1 person out of (*n* + 1) available for selection. This can be done in \({}^{n + 1}{C_1}\) ways.

**( r + 1)**

**The**

*r*-group contains \({A_1},\,\,{A_2}...{A_r}\)In this case, our *r*-group is already complete. We need not select any more person. This can be done in \({}^n{C_0}\) or equivalently 1 way.

Convince yourself that these (*r* + 1) cases cover all the possible cases that can arise in the formation of the * r* - groups. Also, all these cases are mutually exclusive. Thus, adding the number of possibilities of each case will give us the total number of *r*- groups possible, i.e.

\[{}^n{C_0} + {}^{n + 1}{C_1} + {}^{n + 2}{C_2} + ... + {}^{n + r - 1}{C_{r - 1}} + {}^{n + r}{C_r} = {}^{n + r + 1}{C_r}\]

**Example – 19 **

How many distinct throws are possible with a throw of *n* dice which are identical to each other, i.e. indistinguishable among themselves ?

**Solution:** The important point to be realised here is that the dice are totally identical. Suppose we had just 2 dice, say die *A* and die *B*. Suppose that, upon throwing these dice, we get a “two” on *A* and a “three” on *B*. This case would be the same as the one where we get a “three” on *A* and a “two” on *B* because we cannot distinguish between *A* and *B*. What we are concerned with is only what numbers show up on the top of the dice. We are not concerned with which die shows what number. This means that if we have *n* dice and we throw them, we are only concerned with how many “ones”, “twos”, “threes” etc show on the top faces of the dice; we are not at all interested in which die throws up what number.

If we denote the number of “ones” we get by \({x_1}\) , number of “twos” we get by \({x_2}\) and so on, we will have

\[{x_1} + {x_2} + ... + {x_6} = n\]

Thus, the total number of distinct throws will be simply the number of non-negative solutions to this integral equation.

As discussed earlier, this number will be \({}^{n + 6 - 1}{C_{6 - 1}} = {}^{n + 5}{C_5}\) .

What would be the number of distinct throws if the *n* dice were not identical?