Examples on Permutations and Combinations Set 2

Go back to  'P & C, Binomial Theorem'

Example – 9

(a)  Consider the set of letters \(\left\{ {a,a,a,b,c,d} \right\}.\)  How many permutations of this set exist?

(b)  Consider the set of letters    \(\left\{ {a,a,a,b,b,c,d,e} \right\}.\) How many permutations of this set exist?

(c)  Generalise the results of the previous two parts. If we have a set of   \(\left( {m + n + p + .....} \right)\)  things where a particular thing, say X, is repeated m times, Y is repeated n times, Z is repeated p times, and so on, find the number of permutations of this set.

Solution:   The main issue now is that we have a repetition of things. If the things we have were all different, the number of permutations would have been easy to calculate. But now, with repetition of things, the number of permutations will change (it will actually decrease, if you think about it carefully). Let us calculate the permutations in this case from first principles

(a) We have 3 (repeated) “a” letters, a “b, a “c” and a d”. In all, 6 letters. Consider, for a moment, that the 3 “a” s are all different. Let us denote the 3 different “a”s by a1 , a2  and a3 . Our set of letters is now  \(\left\{ {{a_1},{a_2}\,,{a_3},b,c,d} \right\}.\) The number of permutations of this set is simply \(^6{P_6} = 6!\)

If we list down all these 6! permutations, we will see that 6 permutations from this list will correspond to only one permutation, had the “a”s been all the same. Why?

Consider any particular permutation with the “a” s all different, say \(\left\{ {b,{a_1},{a_2},c,{a_3},d} \right\}.\)  If  we fix the letters “b”, “c” and “d”, the 3 different “a” s can be permuted amongst themselves in  \(3! = 6\) ways. We now list down all the 6 permutations so generated on the left hand side in the figure below, and see that these 6 permutations correspond to a single permutation if the “a” s were all the same:

\[\left. \begin{gathered}   b\,\,\boxed{{a_1}}\,\,\boxed{{a_2}}\,\,\,c\,\,\,\boxed{{a_3}}\,\,d \hfill \\b\,\,\boxed{{a_1}}\,\,\boxed{{a_3}}\,\,\,c\,\,\,\boxed{{a_2}}\,\,d \hfill \\b\,\,\boxed{{a_2}}\,\,\boxed{{a_1}}\,\,\,c\,\,\,\boxed{{a_3}}\,\,d \hfill \\b\,\,\boxed{{a_2}}\,\,\boxed{{a_3}}\,\,\,c\,\,\,\boxed{{a_1}}\,\,d \hfill \\b\,\,\boxed{{a_3}}\,\,\boxed{{a_1}}\,\,\,c\,\,\,\boxed{{a_2}}\,\,d \hfill \\b\,\,\boxed{{a_3}}\,\,\boxed{{a_2}}\,\,\,c\,\,\,\boxed{{a_1}}\,\,d \hfill \\ \end{gathered}  \right\}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,b\,\,a\,\,a\,\,c\,\,a\,\,d\]

The 6 permutations on the left with different “a”s as correspond to a single permutation with the “a” s all same.

Fig -  6

Thus, the actual number of permutation with the “a”s all same will be

\[\frac{{6!}}{{3!}} = \frac{{6!}}{6} = 120\]

(b) We now have 3 repeated “a” s and 2 repeated “b” s, and a total of 8 letters. If we for a moment take the “a” s and “b” s as all different, the total number of permutations of this set of 8 letters would be  \(^8{P_8} = 8!\)

However, once we list down these 8! permutations, we will see that (as in the previous part) 3!=6 permutations in this list will correspond to a single permutation   if the “a”s were all the same. Similarly, 2!=2 permutations in this list will correspond to a single permutation if both the “b”s were the same. Thus, the actual number of permutations if “a”s and “b”s were the same would  be \(\begin{align}\frac{{8!}}{{3!2!}}\end{align}\)

(c)These results can now easily be generalized for this general set and the number of permutations will be

\[\frac{{(m + n + p + .....)!}}{{m!n!p!......}}\]

From this example once again, the power of the fundamental principle of counting should be quite evident. Using a logical development/extension of this principle, we see that we’ve been able to solve non-trivial questions like the one above.

Example – 10

Consider the integral equation \({x_1} + {x_2} = 4\;where\;{x_1},{x_2} \in \mathbb{Z}\) . The non-negative solutions to this equation can be listed down as \(\left\{ {0,4} \right\},\left\{ {1,3} \right\},\left\{ {2,2} \right\},\left\{ {3,1} \right\}and\left\{ {4,0} \right\}\) . Thus, 5 non-negative integral solutions exist for this equation.

We would like to solve the general case. How many non-negative, integral solutions exist for the equation

\[{x_1} + {x_2} + ..... + {x_n} = r\]

Solution:         You might be surprised to know that this question can be solved using the general  result obtained in the previous example. Can you think how?

Let us consider an arbitrary integral equation, say   \({x_1} + {x_2} + {x_3} = 8.\)  Consider any particular non-negative integral solution to this equation, say \(\left\{ {2,3,3} \right\}\) . We some how need to “tag” this solution in a new form; a form which is easily countable. This is how we do it. We break up the solution     2 + 3 + 3 = 8 as shown below:

\[11\,\,\boxed{ }\,\,\,1\,11\,\,\,\boxed{ }\,\,\,111 = 8\qquad\qquad...\left( 1 \right)\]

Similarly, 1 + 6 + 1=8 would be written as

\[1\,\,\boxed{ }\,\,\,1\,11111\,\,\,\boxed{ }\,\,1 = 8\qquad\qquad...\left( 2 \right)\]

and            0 + 1 + 7 = 8  would be written as

\[\boxed{ }\,\,\,1\,\,\,\boxed{ }\,\,1111111 = 8\qquad\qquad...\left( 3 \right)\]

and            0 + 0 + 8 = 8 would be written as

\[\boxed {  }\,\,\,\boxed{  }\,\,11111111 = 8\qquad\qquad...\left( 4 \right)\]

An alert reader must have realised the ‘trick’ by now. In each of (1), (2), (3) and (4), we have on the left hand side 8 “1” symbols and 2 “ \(\boxed{ }\) ” symbols, in different orders. Any non-negative integral solution can thus be represented by a unique permutation of 8 “1” symbols and 2 “\(\boxed{ }\)” symbols. Conversely, every permutation of 8 “1” symbols and 2 “ \(\boxed{ }\) ” symbols represents a unique non-negative integral solution to the equation .

Thus, the set of non-negative integral solutions to the equation and the set of permutations of 8 “1” symbols and 2 “ \(\boxed{ }\) ” symbols are in one-to-one-correspondence. To count the required number of solutions, we simply count the permutations of 8 “1” symbols and 2 “ \(\boxed{ }\) ” symbols, which as described in the last example would be \(\begin{align}\frac{{(8 + 2)!}}{{8!2!}} = \frac{{10!}}{{8!2!}} = 45\end{align}\)

This beautiful artifice described about  should make it clear to you the significance of (and the challenge of producing!) elegant proofs/solutions.

We now generalise this result. Any non-negative integral solutions to the equation  can \({x_1} + {x_2} + ..... + {x_n} = r\) be represented using r “1” symbols and n – 1 “ \(\boxed{ }\) ” symbols. The total number of permutation of these symbols will be

\[\frac{{(n + r - 1)!}}{{r!(n - 1)!}} = {\,^{n + r - 1}}{C_r}\]

and hence, this is the required number of solutions.

Example – 11

Consider a rectangular integral grid of size \(m \times n.\)   For example,  a   \(4 \times 5\)  integral grid is drawn alongside:

A person has to travel from point A(0, 0) to the diagonally opposite  point C(m, n). He moves one step at a time, towards the east or   towards the north (that is, never moves towards the west or south  at any time). How many distinct paths exist from the point A to the point C?

Solution:   Let us draw a random path on our \(4 \times 5\)  grid in Fig. 6  and think of some way to mathematically specify/describe this path

Suppose you had to describe this path to a blind person. If you use E for a step towards the east  and N  for a step towards the north, you’d tell the blind person that the travelling person took the following path.

 

\[\mathbf{“\;E \; E\; N\; E\; N\; E\; E \;N\; N\;”}\]

This string that we just formed should immediately make you realise how to calculate the number all the possible paths. We have 5 “E” steps and 4 “N” steps. Any permutation of these 9 steps gives rise to a different unique path. For example, the string \(\mathbf{“\;E \; E\; E\; E\; E\; N\; N \;N\; N\;”}\) is the path that goes straight east from A to B and then straight north from B to C. Thus, any path can be uniquely characterised by a permutation of these 9 steps. The number of permutations of these 9 letters, 5 of which are “E”s and 4 are “N”s, is \(\begin{align}\frac{{9!}}{{5!4!}}\end{align}\) . This is therefore the number of different paths that the travelling person can take from A to C. For an \(m \times n\)  grid we will have (m + n) total steps, m of them being “E” s and the remaining n being “N” s Thus, the number of possible paths is \(\begin{align}\frac{{(m + n)!}}{{m!\, \times \,n!}}\end{align}\)

Example – 12

(a)  We have m apples, n oranges and p bananas. In how many ways can we make a non-zero selection of fruit from this assortment?

(b) How many factors does 144000 have? In general, how many factors does a natural number N have?

Solution:   These two seemingly unrelated questions have exactly the same approach to their solutions! Before reading the solution, can you imagine how?

(a)    The most important point to realise in this question is the nature of objects to be selected. We have m apples. These m apples are exactly identical to each other. You cannot make out one apple from another. This means that if you have to choose r apples out of n, there’s only one way of doing it:  you just pick (any of the) r apples. It doesn’t matter which  apples you choose, because all the apples are identical. Thus, only 1 r-selection is possible. So how many total selections are possible? We either select 0 apples, 1 apple, 2 apples, .... r apples, ... or m apples. Thus (m + 1) ways exist to select apples.

\[\left\{ \begin{array}{l}{\rm{Make\; sure \;you\; properly \;understand\; the \;essence\; of\; this\; discussion\;  and \;why\; }}\\{\rm{choosing\; }}r{\rm{ \;apples\; out\; of\; }}n\,\,{\rm{can\; be\; done \;in\; only\; 1\; and \;not\;}}{{\rm{ }}^n}{C_r}{\rm{ \;ways}}{\rm{.}}\end{array} \right\}\]

We therefore have (m + 1) ways to select apples, (n +1) ways to select oranges and (p + 1) ways to select bananas. The selection of a particular fruit is independent of the selection of another fruit.

Hence, we have (m +1) (n +1) (p +1) ways to select a group of fruit.

But wait! In the (m +1) ways of selecting apples, there’s also one way in which we select no apple. Similarly, in the (n + 1) ways of selecting oranges, there’s one in which we select no orange, and in the (p + 1) ways of selecting bananas, there’s one in which we select no banana. Thus, in the product (m +1) (n +1) (p +1), there’ll be one case involving no fruit of any type. We have to exclude this case if we want a non-zero selection of fruit.

Therefore, the number of ways of making a non-zero selection is (m +1)(n +1)(p +1) —1.

(b) You might be wondering how the factors problem is related to the first part! Read on.

Lets consider a smaller number first. Take 60, for example, and list down all its factors   (including 1 and 60):

\[\left\{ {1,2,3,4,5,6,10,12,15,20,30,60} \right\}\]

From elementary mathematics, you know that any number can be factorized into a product of primes. For example, 60 can be written in its prime factorization from as:

\[\begin{align}&60 = 2 \times 2 \times 3 \times 5\\&\,\,\,\,\,\, = {2^2} \cdot {3^1} \cdot {5^1} \end{align}\]

Such a representation exists for every natural number N. Can we somehow use this representation to find the number of factors?

Consider any factor of 60, say 12, The prime factorization from of 12 is \({2^2} \cdot {3^1}\)  . Similarly, this representation for 15,  for example, is \({3^1} \cdot {5^1}\)  and for 30 would be \({2^1} \cdot {3^1} \cdot {5^1}\)  .

With discussion in our mind, we rephrase  our problem: We have 60 whose prime representation is \({2^2} \cdot {3^1} \cdot {5^1}\) . Thus, we have 2 twos, 1 three and 1 five with us. (You could imagine that we    have 2 apples, 1 orange and 1 banana).

To form a factor of 60, what we have to do is to make a selection of prime factors from amongst the available prime factors. For 60, we have 2 twos (apples), 1 three (orange) and 1 five(banana). In how many ways can we make our selection?

The last part tells is that we can do it in  \((m + 1)(n + 1)(p + 1)\) ways or \((2 + 1)(1 + 1)(1 + 1) = 12\)  in this particular case. (We also allow no selection of any prime factor - this corresponds to the factor 1 of 60)

Do you feel the elegance of this solution?

For the general case of a natural number N whose prime representation is of the   form  \(p_1^{{\alpha _1}}p_2^{{\alpha _2}}........p_n^{{\alpha _n}},\) the number of factors (including 1 and N) is

\[({\alpha _1} + 1)({\alpha _2} + 1)........({\alpha _n} + 1)\]

For example, 144000 can be represented as

\[144000 = {2^7} \cdot {3^2} \cdot {5^3}\]

The required number of factors is

\[(7 + 1)(2 + 1)(3 + 1) = 96\]

Learn math from the experts and clarify doubts instantly

  • Instant doubt clearing (live one on one)
  • Learn from India’s best math teachers
  • Completely personalized curriculum