Examples - Practical Counting Situations

Let us apply the FPC to a few examples. You are urged to first work out each question on your own, and only go through the solution when either you think you have arrived at the correct answer, or you have been unable to solve the problem after attempting it multiple times.

Example 1: A hall has 8 doors. In how many ways can a person enter the hall through one door and exit through a different door?

Solution: The person has 8 options to enter the hall. For each of these 8 options, he has 7 options to exit the hall. Thus, he has \(8 \times 7 = 56\) ways to enter and exit from different doors.

Example 2: Aanan has 6 flags of different colors. How many different signals can he generate, if each signal requires two flags, one below the other?

Solution: Aanan has 6 options for the top flag. Once he has chosen the top flag, he has 5 options for the bottom flag. Thus, he can generate \(6 \times 5 = 30\) different signals using these 6 flags.

Example 3: In an objective type test, there are five questions. The first three questions have 4 options, while the last two questions have 5 options. How many different answer sequences are possible?

Solution: Each of the first three questions can be answered in 4 ways. Each of the last two questions can be answered in 5 ways. Thus, the number of different answer sequences possible is

\[4 \times 4 \times 4 \times 5 \times 5 = 1600\]

Example 4. Find the number of three digit numbers in which all the digits are distinct.

Solution: Suppose that we have to form a three digit number with distinct digits. In how many ways can we do so? There are 10 different digits from 0 to 9.

1. We can select the digit at the hundreds place in 9 ways (we cannot select 0 for the hundreds place).

2. Once we have selected the digit at the hundreds place, we have 9 options for the digit at the tens place (we exclude the digit we selected for the hundreds place).

3. Similarly, we now have 8 options for the digit at the units place.

Thus, the total number of three digit numbers with distinct digits is

\(9 \times 9 \times 8 = 648\)

Example 5: Answer these:

(a) How many three digit numbers are there in which 6 is at the units place?

(b) How many three digit numbers have exactly one 6?

(c) How many three digit numbers have at least one 6?

Solution: 

(a) Once we fix 6 at the units place, we have 10 options to select the digit at the tens place, and 9 options to select the digit at the units place. Thus, there are \(10 \times 9 = 90\) numbers with 6 at the units place.

(b) There are three different possibilities in this case:

1. The 6 is at the units place. Then, we have 9 options for the tens digit and 8 options for the hundreds digit (why?). Thus, there are \(9 \times 8 = 72\) such numbers.

2. The 6 is at the tens place. There will be another 72 such numbers.

3. The 6 is at the hundreds place. Then, we have 9 options for the tens place as well as 9 options for the units place (how?). Thus, there are \(9 \times 9 = 81\) such numbers.

The total number of numbers with exactly one 6 is \(72 + 72 + 81 = 225\).

(c) To calculate this, we first calculate the total number of three digit numbers. We have 9 options to select the hundreds digit, then 10 options to select the tens digit, and 10 options to select the units digit. Thus, there are \(9 \times 10 \times 10 = 900\) three digit numbers.

Now, we calculate the number of numbers with no 6. We have 8 options to select the hundreds digit, 9 options to select the tens digit, and 9 options to select the units digit. Thus, there are \(8 \times 9 \times 9 = 648\) such numbers.

Now, the number of numbers with at least one 6 can be calculated as the difference of the total number of three digit numbers and the number of numbers with no 6. Thus, the required number is \(900 - 648 = 252\).

Example 6: A coin is tossed four times in succession. The sequence of outcomes is recorded. How many different such sequences are possible? List these sequences.

Solution: Each toss can lead to two outcomes: H (Heads) or T (Tails). Thus, the number of different sequences possible is \(2 \times 2 \times 2 \times 2 = 16\). These 16 sequences are listed below, organized by the number of Heads in the sequence:

No H	TTTT
One H	HTTT, THTT, TTHT, TTTH
Two H	HHTT, HTHT, HTTH TTHH, THTH, THHT
Three H	HHHT, HHTH, HTHH, THHH,
Four H	HHHH

Example 7:

(a) A rolling die is rolled twice (in succession), and the sequence of two numbers which show up is recorded. How many distinct outcomes are possible?

(b) Three rolling dice are rolled simultaneously. How many distinct outcomes are possible?

Solution: 

(a) An outcome is a sequence of two numbers, each in the set {1, 2, 3, 4, 5, 6}. For example, the outcome {3, 4} means that one the first roll, 3 showed up, and on the second roll, 4 showed up. There are 6 possible numbers which can show up on the first roll, and similarly, 6 possible numbers for the second roll. Thus, the number of distinct outcomes is \(6 \times 6 = 36\).

(b) In this case, an outcome would be a set of three numbers, each in the set {1, 2, 3, 4, 5, 6}. For example, {3, 6, 4} is a possible outcome, which means that 3 showed up on the first die, 6 on the second die and 4 on the third die. Clearly, the number of distinct outcomes is \(6 \times 6 \times 6 = 216\).

Example 8: You have n different objects, and two boxes. In how many different ways can you put these objects into the boxes such that no box remains empty?

Solution: We have 2 options for each object. The first object can be stored in 2 ways: either into the first box or into the second box. Similarly, the second object can be stored in 2 ways, and so on. Thus, the n objects can be stored in the two boxes in

\[2 \times 2 \times 2 \times ... \times 2 = {2^n}\]

ways. However, this number also counts the 2 cases where either box remains empty. Thus, the number of ways of storing in which no box remains empty, is \({2^n} - 2\).

Let us apply this result to a specific example to see whether it yields the correct answer. Take n = 3, which means that there are 3 distinct objects; name them A, B and C. The following table shows the number of ways of distributing these 3 objects into two boxes such that no box remains empty:

Box-1	Box-2
A	B,C
B	C, A
C	A, B
A, B	C
B, C	A
C, A	B

We count 6 possible distributions, the same result which the formula we derived gives us:

\[{2^n} - 2 = {2^3} - 2 = 6\]

Example 9: You have 10 distinct objects, and 4 boxes. In how many ways can you distribute the objects into the boxes so that the first box has exactly one object? Note that the other boxes may or may not be empty.

Solution: Let us first choose one object for the first box, Box-1. This can be done in 10 ways. Now we have 9 objects left. For each of these 9 objects, we have 3 options to store it: Box-2, Box-3 or Box-4. Thus, the total number of ways of distributing the 10 objects is

\[10 \times \underbrace {3 \times 3 \times ... \times 3}_{9{\rm{ times}}} = 10 \times {3^9}\]

Example 10: Find the number of four letter words, with or without meaning, which can be formed using the letters of the word ROSE, when repetition of letters is

(a) not allowed

(b) allowed

Solution:

(a) When repetition of letters is not allowed, we have 4 options to select the first letter, 3 options to select the second letter, 2 options to select the third letter and 1 option to select the fourth letter. Thus, we can form \({\rm{4}} \times {\rm{3}} \times {\rm{2}} \times {\rm{1 = 24}}\) different words in this case.

(b) When repetition of letters is allowed, we have 4 options to select each of the four letters. Thus, the number of words we can form in this case is \(4 \times 4 \times 4 \times 4 = 256\).

Example 11: How many words (with or without meaning) can be formed by using all letters of the word HOUSE?

Solution: We have 5 different letters and 5 spaces to be filled: __ __ __ __ __.

We have 5 options to select the first letter, 4 options to select the second letter, 3 options to select the third letter, 2 options to select the fourth letter, and 1 option to select the fifth letter. Thus, the number of words which can be formed is: \(5 \times 4 \times 3 \times 2 \times 1 = 120\).

In general, if a word has n letters (all distinct), then the number of words which can be formed using the letters of this word is:

\[n \times \left( {n - 1} \right) \times \left( {n - 2} \right) \times ... \times 2 \times 1\]

This product is represented concisely as \(n!\). For example:

\[\begin{array}{l}2! = 2 \times 1 = 2\\3! = 3 \times 2 \times 1 = 6\\4! = 4 \times 3 \times 2 \times 1 = 24\\5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\\6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720\end{array}\]

Note that \(n! = n \times \left( {n - 1} \right)!\).

Example 12: Find the number of words which can be formed from the letters of the word EDUCATION, which

(a) consist of all the letters of this word

(b) start with E and end with N

(c) contain the string “CAT”

(d) have the letters C, A and T occurring together

(e) start and end with vowels

(f) have no two vowels occurring together.

Solution:

(a) We have 9 letters in the word, and all are different. Thus, the total number of 9-letter words which can be formed is 9!.

(b) We fix E at the start and N at the end of the word:

E __ __ __ __ __ __ __ N

We now have 7 places, which we need to fill with the remaining 7 letters. This can be done in 7! different ways. Thus, the number of words which start with E and end with N is 7!.

(c) We want all those words in which the string “CAT” occurs. Let us treat “CAT” as a single object, since we want “CAT” to appear as a single entity. Thus, we have the following different objects:

E    D   U    C    A    T     I     O    N

These are 7 different objects, and we can order them in 7! ways. Thus, the number of words which contain “CAT” is 7!.

(d) We now need the words which contain the letters C, A and T occurring together. This means that they can occur together in any order. There are 3! = 6 ways in which C, A and T can be arranged among themselves, namely CAT, CTA, ACT, ATC, TAC, and TCA.

Now consider from the previous part all those words in which the string “CAT” occurs. These are 7! in number. Corresponding to each such words, we can have 6 arrangements in which the constraint is that C, A and T occur together. This is because the string “CAT” can itself be ordered in 6 ways as described above. For example, consider the word “EDUCATION“; to this word will correspond 6 words in which C, A and T occur together:

\[{\rm{EDU}}{\fbox{CAT}}{\rm{ION}}\left\{ \begin{array}{l} {\rm{EDU}}{\fbox{CAT}}{\rm{ION}}\\ {\rm{EDU}}{\fbox{CTA}}{\rm{ION}}\\ {\rm{EDU}}{\fbox{ACT}}{\rm{ION}}\\ {\rm{EDU}}{\fbox{ATC}}{\rm{ION}}\\ {\rm{EDU}}{\fbox{TAC}}{\rm{ION}}\\ {\rm{EDU}}{\fbox{TCA}}{\rm{ION}} \end{array} \right.\]

Thus, the number of words in which C, A and T occur together is \(7! \times 3!\).

(e) In the word EDUCATION, there are a total of 5 vowels. We want to have the starting and ending letters of our words as vowels. Let us first arrange the starting and ending letters and then fill in the rest of the 7 places. Out of the 5 vowels available to us, the first and the last place can be filled in \(5 \times 4 = 20\) places. Once we’ve fixed the first and the last letters, the remaining 7 places can be filled in 7! ways. Thus, the total number of required words is \(20 \times 7!\).

(f) There are 5 vowels and 4 consonants in the word EDUCATION. We require words in which no two vowels occur together. We can ensure such arrangements by first fixing the 4 consonants and then arranging the 5 vowels in the 5 possible places that arise as depicted in the following figure.

\[{{\fbox{ }}\;\rm{D}}\;{\fbox{ }}\;{\rm{C}}\;{\fbox{ }}\;{\rm{T}}\;{\fbox{ }}\;{\rm{N}}\;{\fbox{ }}\]

Convince yourself that any arrangement of the 5 vowels in the 5 blank spaces above will correspond to a word with no two vowels together. The number of ways of arranging the 4 consonants is 4!. After the consonants have been arranged, the number of ways of arranging the 5 vowels in the 5 blank spaces as depicted in the figure above is 5!. Thus, the required number of words is \(4! \times 5!\)