Permutations and Combinations

Permutations and combinations is a very interesting chapter and gives us food for thought.  Most problems can be solved in multiple ways. Combination of different techniques and our application of ideas is what determines our command over this topic.  More over, this topic is very important in learning "Probability" so study the problems with enthusiasm.
It is always confusing for some, when to use permutation and when to use combination.

Combination or selection:
In your college, your college management is planning to form an "anti ragging" committee.   There are 3 persons who are interested to be a part of that committee.  But the management is thinking of keeping only 2 in the committee.  In how many ways this can be achieved?
Our possible combinations are:

AB, BC, AC

Only 3 are possible.  We don't consider selection of AB and BA are two different ones.  Whether you choose A first and B next or B first and A next may not make any difference.

So remember, When there is a selection like Committee, You have to select r persons/ objects from n persons / objects, we use ${}^n{C_r}$ observe the C in both.
Selection of 3 out of 5 is represented as ${}^5{C_3}$ which is equal to ${}^5{C_2}$ as ${}^n{C_r} = {}^n{C_{n - r}}$
How do we write ${}^5{C_3}$
Text book notation for ${}^n{C_r} = \displaystyle\frac{{n!}}{{r!(n - r)!}}$ but we hardly use this formula to calculate ${}^5{C_3}$ or any other selection
Simply we do like this. we write 5 in the descending order upto 3 times and divide it by 3!
So ${}^5{C_3} = \displaystyle\frac{{5 \times 4 \times 3}}{{3 \times 2 \times 1}} = 10$
Or we know that ${}^n{C_r} = {}^n{C_{n - r}}$ so ${}^5{C_3} = {}^5{C_{5 - 3}} = {}^5{C_2}$
Now ${}^5{C_2} = \displaystyle\frac{{5 \times 4}}{{2 \times 1}}$ = 10

Permutation or Arrangement:
Now, We have to take a photo graph of our newly formed committee and put it in the notice board. How do we do that?
Now 6 different arrangements AB, BA, AC, CA, BC, CB are possible.
Whenever there is an arrangement, we use the formula ${}^n{P_r}$ as like in Photograph where arrangement is possible
So selection of r objects from n objects and arranging them in r positions will be ${}^n{P_r}$.
Rather than using this formula, you can first select r objects from n, using ${}^n{C_r}$ and multiply it by r! as it arranges r objects in r positions.
Therefore, ${}^n{P_r} = {}^n{C_{n - r}} \times r!$
Note: When we have to arrange r objects in r positions, this can be done in r! ways. When there are repeatations we have to divide r! with those repetitions

Solved Examples

(Problems on alphabets)

Solved Example 1:
1. How many arrangements can be made of the letters of the word “ASSASSINATION”? In how many of them are the vowels always together?
Solution:
In the word “ASSASSINATION”, n (total no.of objects) = 13, among them we have four S, three A, two N and two I. So total no.of possible arrangements of these 13 objects = $\displaystyle\frac{{13!}}{{4! \times 3! \times 2! \times 2!}}$ = $\displaystyle\frac{{13!}}{{4! \times 4 \times 3!}}$ = $\displaystyle\frac{{13!}}{{4{!^2}}}$
If vowels are always together,  we can say that all the vowels taken together (AAAIIO) will be behaving like a single object, than total no.of objects will be 8 (four, S, two N, one T and one group of vowels). Total no.of arrangements for these eight objects will be 8!/(4!x2!). Now the vowels altogether can be arranged in 6!/(3!x2!) ways so the total no.of arrangements of given 13 objects when vowels are always together is $\displaystyle\frac{{8! \times 6!}}{{4! \times 3! \times 2! \times 2!}}$ = $\displaystyle\frac{{8! \times 6!}}{{4{!^2}}}$

Solved Example 2:
2. In how many ways can the letters of the word ARRANGE be arranged so that
Solution:
By using the following equation we can get the required answer
Two R’s are never together = Total possible arrangements - Two R’s are always together
Total words = $\dfrac{{7!}}{{2!2!}}$ = $\dfrac{{7 \times 6 \times 5 \times 4 \times 3 \times 2}}{{2 \times 2}}$ = 1260
R’s together $\displaystyle\frac{{{\rm{6}}!}}{{{\rm{2}}!}}$ = 6 x 5 x 4 x 3 = 360
R’s never together = 1260 - 360 = 900
(b) The Two A’s are together but not two R’s = Two A’s are always together - (Two R’s and two A’s are always together)
Two A’s together => $\displaystyle\frac{{{\rm{6}}!}}{{{\rm{2}}!}}$ = 360
Also two R’s together = 5! = 120
Ans = 360 - 120 = 240
(c) Neither 2 A’s or 2R’s are together = total possible arrangements - {(two A’s are always together + Two R’s are always together) - Both Two A’s and Two R’s are always together}
Either 2A’s or 2R’s or both A’s & R’s are together = 600
Hence None of these together = 1260 - 600 = 660.

Solved Example 3:
Ten different alphabets are given. Words containing five alphabets are to be formed from them. Find the number of words which have exactly one alphabet repeats.
Solution:
We have 10 alphabets, we are to form five alphabet’s word, and given that repetition of exactly one alphabet is allowed. We can choose that alphabet in 10 ways. Now, following cases are possible:
1. It repeats exactly two times: Number of words will be 10 x $^{\rm{5}} {\rm{C}}_{\rm{2}}$ x 9 x 8 x 7 = 50400
2. It repeats exactly three times: Number of words will be 10 x $^{\rm{5}} {\rm{C}}_{\rm{3}}$ x 9 x 8 = 7200
3. It repeats exactly four times: Number of words will be 10 x $^{\rm{5}} {\rm{C}}_{\rm{4}}$ x 9 = 450
4. It repeats exactly five times: Number of words will be 10 x $^{\rm{5}} {\rm{C}}_{\rm{5}}$ = 10
Total number of words with only one alphabet repeating = 58060
Moreover, total number of words that can be formed if repetition is not allowed is $^{{\rm{10}}} {\rm{P}}_{\rm{5}}$ and if repetition is allowed total number of words that can be formed will be ${\rm{10}}^{\rm{5}}$. ${\rm{10}}^{\rm{5}} {\rm{ - }}^{{\rm{10}}} {\rm{P}}_{\rm{5}}$ gives the number of words having atleast one alphabet repeating.

Solved Example 4:
4. How many 4 letter words may be formed by using the letters of the word "ASSASSINATION"

Solution:
We have (AAA) (SSSS) (II) (NN) T O N --- 6 different letters
We can choose 4 letter words in the following ways
a. All the 4 letters are different - abcd
we can choose 4 letters form 6 catogories in ${}^6{C_4}$ ways and these 4 arranged in 4! ways so total = ${}^6{C_4}$ x 4!
b. 2 letters same and 2 are different - aabc
We can choose the repeated letter in ${}^4{C_1}$ way and the 2 distinct letters from the remaining 5 catogories in ${}^5{C_2}$ and we arrange them into $\displaystyle\frac{{4!}}{{2!}}$ ways. So total ways are ${}^4{C_1} \times {}^5{C_2} \times \frac{{4!}}{{2!}}$
c. 2 letters repeat twice - aabb
We choose the repeated letters from 4 catogories in ${}^4{C_2}$ ways. And we arrange them in $\displaystyle\frac{{4!}}{{2! \times 2!}}$ ways. So total $^4{C_2} \times \displaystyle\frac{{4!}}{{2! \times 2!}}$
d. 1 letter repeat thrice - aaab
We choose the repeated letter in ${}^2{C_1}$ way and remianing letter in ${}^5{C_1}$ way.  and we arrange them in ${}^2{C_1} \times {}^5{C_1} \times \displaystyle\frac{{4!}}{{3!}}$
e. 1 letter repeat 4 times - aaaa
We choose the letter in only one way (only S we can choose) and we arrange them in 1 way.

Problems on Numbers

Solved Example 5:
Using the digits of the decimal system, how many numbers lying between 5000 and 6000 (both inclusive), can be formed if,
(i) Repetition of digits is not allowed.
(ii) Repetition of digits is allowed.
Solution:
(i) If we are to form the numbers without repeating any digit then we can’t take 5000 and 6000 as 0 is repeating. Now if number is between 5000 and 6000, we can say that thousand’s place can take only one digit that is 5. For hundred’s place we are left with only 9 digits, for ten’s place only 8 digits and for unit’s place only 7 digits. So the total number of numbers between 5000 and 6000 in which no digit is repeating will be 9 x 8 x 7 = 504
(ii) Now if the repetition of digits is allowed, we can include all the numbers right from 5000 up to and with 6000. So the total number of numbers will be 1001. Hence, the answer is option (b).

Solved Example 6:
How many numbers greater than a million can be formed by using the digits 2, 3, 0, 3, 5, 2, 3 which will be divisible by 5?
Solution:
We have 7 digits (objects), 2, 3, 0, 3, 5, 2, 3 (Two times 2 and three times 3) and we have to form the numbers greater than 1,000,000 and completely divisible by 5. Now as the number is divisible by 5, two cases are possible:
When unit digit of the number is 0: Rest 6 digits can be arranged on 6 places in 6! ways and as we can see that some digits (objects) are repeating so we can say that possible ways are 6!/3!x2! = 60
When unit digit of the number is 5: Million’s place can not be filled with 0 so to fill million’s place only 5 ways are there and rest 5 places can be filled with remaining 5 digits in 5! ways and again taking repetition into consideration we can say that total number of ways are 5x5!/3!x2! = 50.
Total number of ways to form the required number = 60 + 50 = 110

Solved Example 7:
What is the sum of all five digit numbers formed by 2, 3, 4, 5, 6 without repetition?
Solution:
Short cut: Use this formula: (n – 1)! × (1111...n times) × (Sum of the digits)
Here n is the number of distinct digits given.
Detailed Explanations:
We have five digits 2, 3, 4, 5 and 6 we have to calculate the sum of all the five digit numbers, which can be formed by using only these 5 digits without repetition. To do that we proceed in the following way:
If 2 is fixed at unit’s place then rest of the digits can be arranged on remaining 4 places in 4! ways. So, if 2’s position is fixed at any place we can form 4! numbers and this also remains true if we fix the position of any other digit.
Sum of all 2’s at unit’s place will be 2x4!, sum of all 3’s at units place will be 3x4!, sum of all 4’s at unit’s place will be 4x4!, sum of 5’s at unit’s place will be 5x4! and sum of all 6’s at unit’s place will be 6x4!. So, the sum of all the digits at unit’s place is 2x4! + 3x4! + 4x! + 5x4! + 6x4! = 20x4!
20x4! is the sum of all the digits at unit’s place, at ten’s place, at hundred’s place, at thousand’s place and at ten thousand’s place also. Now to find the sum of all the numbers we have to multiply these sums of digits at different places with their respective place values.
Sum of all the numbers
= 20×4!×10000 + 20 × 4! × 1000 + 20 × 4! × 100 + 20 × 4! × 100 + 20 × 4! × 1
= 20 × 4! × (10000 + 1000 + 100 + 10 + 1)
= 20 × 4! × 11111

Solved Example 8:
Find the sum of all the five digit numbers formed by the digits 2, 4, 6, 8, 0 when
(i) Repetition of the digits is not allowed
(ii) Repetition is allowed.
Solution:
(i) Use this following short cut:
(n – 1)! × (111... n times) × (sum of the digits) – (n – 2)! × (111... (n – 1) times) × (sum of the digits)
Detailed Explanation:
Total ways = 4 × 4 × 3 × 2 × 1 = 96,
Sum of digits at unit’s place, ten’s place, hundred’s and thousand’s place
= 0 × 4! + (2 + 4 + 6 + 8) x (4! - 3!)
= 20 × 18
= 360.
Sum of digit at ten thousand’s place
(2 + 4 + 6 + 8) x 24 = 480
Total sum 480 × ${10^4}$ × 360 × ${10^3}$ + 360 × ${10^2}$ + 360 × 10 + 360
= 5199960
(ii) Repetition is allowed.
Use the following Shortcut:
${{n^{n -1}}}$ × (111... n times) × (sum of the digits) –  ${{n^{n - 2}}}$ × (111... (n – 1) times) × (sum of the digits)
Detailed Explanation:
Total ways = 4 × 5 × 5 × 5 ×  5= 2500
Sum of digits at unit, ten’s hundred’s & thousand’s place
(0 + 2 + 4 + 6 + 8) x 500
Sum of digits at ten thousand’s place
(2 + 4 + 6 + 8) x 625 = 20 x 625 = 12500
Total Sum = 12500 × ${10^4}$ × 10000 × ${10^3}$ + 10000 × ${10^2}$ + 10000 × ${10^1}$
= 136110000

Solved Example 9:
I forgot my friend’s 7 digit telephone number, but I remembered that the first two digits of the number are either 25 or 53. Also the number is even and the digit 2 appears once. What is the maximum number of trials I have to make before I can contact my friend?
Solution:
There are two cases; dial 25 or 53 first.
Case I.
First two digits are 25
Then total cases 1 x 1 9 x 9 x 9 x 9 x 4 = ${\rm{9}}^{\rm{4}} {\rm{ \times 4 = 36 \times 9}}^{\rm{3}}$
Case II.
If we start with 53 than either we can put 2 at unit place or at any of the remaining 4 places
Case II (i)
If 2 is at unit place.
Then, 1 × 1 × 9 × 9 × 9 × 1 = ${\rm{9}}^{\rm{3}}$ × 9 ways,
Case II (ii)
If 2 is at any of the remaining 4 place.
Then 1 × 1 × $^{\rm{4}} {\rm{C}}_{\rm{1}} {\rm{ \times 9}}^{\rm{3}} {\rm{ \times 4 = 9}}^{\rm{3}} {\rm{ \times 16}}$ ways
Total ways = ${\rm{9}}^{\rm{3}}$ × 36 + ${\rm{9}}^{\rm{3}}$ × 9 + ${\rm{9}}^{\rm{3}}$ × 16 = 61 × ${\rm{9}}^{\rm{3}}$ ways

Solved Example 10:
How many numbers greater than a billion but less than ${\rm{10}}^{{\rm{10}}}$ can be formed such that the sum of the digits is equal to 3?
Solution:
Here we have 10 digits & we have to find no.of ways such that sum of digits is 3.
Case I
First digit is 1.
Then two one’s can be arranged in
9 places in $^{\rm{9}} {\rm{C}}_{\rm{2}}$ = 36ways
Or a ‘2’ can be arranged in
9 places in $^{\rm{9}} {\rm{C}}_{\rm{1}}$ = 9ways
Case II.
If first digit is 2
Then one ‘1’ can be arranged in remaining 9 places in $^{\rm{9}} {\rm{C}}_{\rm{1}}$ = 9ways
Case III
Only one way is possible if the starting digit is 3.
So total ways = 36 + 9 + 9 + 1 = 55 ways

Solved Example 11:
How many six digit numbers are possible by using the digits 1, 2, 3, 4, 5, 6, 7 without repetition such that they are divisible by 12?
Solution:
To be divisible by 12, a no.should be divisible by both 3 & 4
Sum of all the available digits is 28. We have to pick any six digits such that there sum is divisible by 3. Possible sums less than 28 are 27, 24, 21, 18 and 15. As we have to leave only one digit at a time that’s why 18 and 15 not possible. For the sum to be 21, leave 7. For the sum to be 24, leave 4. For the sum to be 28, leave 1.
Case (i) 1, 2, 3, 4, 5, 6
This no. will be divisible by 4 also if the last two digits are either
12, 16, 24, 32, 36, 52, 56, 64
For all the above 8 cases, remaining 4 digits can be arranged in 4! Ways.
Number of ways = 4! x 8.
Case (ii) 1, 2, 3, 5, 6, 7
Last two digits can be 12, 32, 52, 72, 16, 36, 56, 76
Number of ways = 4! x 8
Case (iii) 2, 3, 4, 5, 6, 7.
Last two digits can be 24, 32, 36, 52, 56, 72, 76 & 64
Number of ways = 4! x 8
Total number of ways = 24 x 4!

Solved Example 12:
All the possible seven digit numbers are formed by using the digits 1, 2, ........., 7 without repetition. These numbers are then arranged in ascending order. What will be the ${\rm{2884}}^{{\rm{th}}}$ number in the given order?
Solution:
Total Possible seven digits numbers = 7! = 5040
Each of these 7 digits will be the starting digits for $\displaystyle\frac{{5040}}{7}$ = 720nos
So 1, 2, 3, 4 will be the starting digits for first 2880 numbers when the numbers are arranged in ascending order. Hence ${\rm{2884}}^{{\rm{th}}}$ number will be 5123674.

Problems on arrangements

Solved Example 13:
In how many ways can a mixed doubles tennis game be arranged from eight married couples, if no husband and wife play in the same game?
Solution:
There are eight married couples or eight males and eight females. First we can select 2 males out of 8 males in $^8 C_2$ ways. Now according to the condition given in the question wives of these 2 males can not be in the same game so we can select any 2 females from the rest 6 females in $^6 C_2$ways. Than taking these four persons we can arrange two different matches by changing the partners.
Hence total no.of matches = $^{\rm{8}} {\rm{C}}_{\rm{2}} {\rm{ \times }}^{\rm{6}} {\rm{C}}_{\rm{2}}$ x 2 = 28 x 15 x 2 = 840

Solved Example 14:
Sixteen persons are to be seated along two sides of a rectangular table with eight chairs on either side. Of these sixteen, Amit, Jaya, Rishi and Neetu with to sit on one side of the table, while Paresh and Sadashiv with to sit on the other, in how many ways can the arrangement be done?
Solution: As shown in the figure there is a rectangular table and sixteen persons are to be seated on the sixteen chairs along two opposite sides of the table, eight chairs on either side. Among these sixteen persons four want to sit on the same side so we can select that side in two ways and as given in the question two other persons want to sit on the other side of the table.
Now after selecting the side for four persons we can arrange them on eight chairs in $^{\rm{8}} {\rm{P}}_{\rm{4}}$ ways, similarly other two persons on the opposite side can be arranged on eight chairs in $^{\rm{8}} {\rm{P}}_{\rm{2}}$ ways. Rest 10 persons can be arranged on remaining 10 chairs in 10! Ways. So the total no.of ways to arrange these 16 persons considering all the conditions = $^{\rm{8}} {\rm{P}}_{\rm{4}} {\rm{ \times }}^{\rm{8}} {\rm{P}}_{\rm{2}}$ x 10! x 2

Solved Example 15:
Six people A, B, C, D, E and F are to be seated at a circular table. In how many ways can this be done if A must always have either B or C on his immediate left and B must always have either C or D on his immediate left?
Solution:
Case 1:
If A has B on his left then B can have either C or D on his left & then remaining 3 persons can arrange themselves in 3! = 6 ways. So total ways are 2 x 6 = 12 ways.
Case 2:
If A has C on his left then B & D will sit such that D is always on left of B & this can be done in 3! = 6.
So Total 18 Ways.

Solved Example 16:
18 chairs are arranged around a hexagon such that there are 3 chairs per side. If 18 men are to be seated on these chairs, then how many different arrangements are possible?
Solution:
The arrangements vary depends on the first person's position where sits in one of the 3 chairs of one side of the hexagon.  He would sit at left, center or right side of the the side of the hexagon.  Observe the position of "J".  If we fix the first person, remaining persons can sit in the remaining chairs in 17! ways. Hence there 3 x 17! Ways.

Solved Example 17:
A new flag is to be designed with seven vertical strips using some or all of the colours Blue, Red, Black, White and Yellow. No two adjacent strips should be of the same colour. The number of ways this can be done such that even numbered strips are of the same colour while two consecutive odd numbered strips are of  different colours is
Solution:
There are 5 ways of choosing a colors for even places.
For ${\rm{1}}^{{\rm{st}}}$ odd place there are 4 ways of choosing a colour from remaining 4 colours for ${\rm{2}}^{{\rm{nd}}}$ odd place there are 3 ways of choosing a colour since two consecutive odd numbered strips should have different colour & similarly there are 3 ways each for ${\rm{3}}^{{\rm{rd}}} {\rm{\& 4}}^{{\rm{th}}}$ odd place.
Hence, total always = 5 x 4 x 3 x 3 x 3 = 540 ways

Dearrangements

Assume n people went to a party wearing hats and while returning no one has picked his own hat. The total ways of doing this can be done by the formula:
${D_n} = n!\left( {\frac{1}{{2!}} - \frac{1}{{3!}} + \frac{1}{{4!}} - ....} \right)$

Solved Example 18:
A father purchased dress for his 3 daughters. The dresses are of same color but different size and they are kept in dark room. In how many ways all the 3 daughters will not choose their own dress?
Solution:
This is a case of de-arrangements = ${D_{n = }}3!\left( {\displaystyle\frac{1}{{2!}} - \displaystyle\frac{1}{{3!}} + \displaystyle\frac{1}{{4!}} - ....} \right)$
So number of ways that none of them chooses their own dress = ${D_{3 = }}3!\left( {\displaystyle\frac{1}{{2!}} - \displaystyle\frac{1}{{3!}}} \right) = 2$

Solved Example 19:
A dispatch clerk prepared 10 letters and 10 addressed envelopes.  What are the total number of ways that exactly 4 letters went into their intended envelope.
Solution:
We can select those 4 letters in ${}^{10}{C_4}$ ways. And the remaining 6 letter go into wrong ones.
So Total ways = ${}^{10}{C_4} \times {D_6}$ = ${}^{10}{C_4} \times 6!\left( {\displaystyle\frac{1}{{2!}} - \frac{1}{{3!}} + \frac{1}{{4!}} - \frac{1}{{5!}} + \frac{1}{{6!}}} \right)$

Miscellaneous Models

Solved Example 20:
A three digit number of the form ‘xyz’ is to be formed such that x > y, x > z, and y < z. How many such numbers are possible if x > 0?
Solution:
According to the conditions given, following table can be obtained easily: Solved Example 21:
On a ABC, on side AB 5 points are marked, on side BC 4 points are marked, while on side AC 3 points are such that none of the points thus marked are on the vertex, then how many triangles can be drawn by joining these points?
Solution:
Out of the given 5, 4 & 3 points on each side, triangles possible are
(i) $^{\rm{5}} {\rm{C}}_{\rm{1}} {\rm{ \times }}^{\rm{4}} {\rm{C}}_{\rm{1}} {\rm{ \times }}^{\rm{3}} {\rm{C}}_{\rm{1}}$ = 5 x 4 x 3 = 60
(ii) $^{\rm{5}} {\rm{C}}_{\rm{1}} {\rm{ \times }}^{\rm{4}} {\rm{C}}_{\rm{0}} {\rm{ \times }}^{\rm{3}} {\rm{C}}_{\rm{2}}$ = 5 x 1 x 3 = 15
(iii) $^{\rm{5}} {\rm{C}}_{\rm{1}} {\rm{ \times }}^{\rm{4}} {\rm{C}}_{\rm{2}} {\rm{ \times }}^{\rm{3}} {\rm{C}}_{\rm{0}}$ = 5 x 6 x 1 = 30
(iv) $^{\rm{5}} {\rm{C}}_{\rm{2}} {\rm{ \times }}^{\rm{4}} {\rm{C}}_{\rm{0}} {\rm{ \times }}^{\rm{3}} {\rm{C}}_{\rm{1}}$ = 10 x 1 x 3 = 30
(v) $^{\rm{5}} {\rm{C}}_{\rm{2}} {\rm{ \times }}^{\rm{4}} {\rm{C}}_{\rm{1}} {\rm{ \times }}^{\rm{3}} {\rm{C}}_{\rm{0}}$  = 10 x 4 x 1 = 40
(vi) $^{\rm{5}} {\rm{C}}_{\rm{0}} {\rm{ \times }}^{\rm{4}} {\rm{C}}_{\rm{2}} {\rm{ \times }}^{\rm{3}} {\rm{C}}_{\rm{1}}$ = 1 x 6 x 3 = 18
(vii) $^{\rm{5}} {\rm{C}}_{\rm{0}} {\rm{ \times }}^{\rm{4}} {\rm{C}}_{\rm{1}} {\rm{ \times }}^{\rm{3}} {\rm{C}}_{\rm{2}}$ = 1 x 4 x 3 = 12
= 60 + 15 + 30 + 30 + 40 + 18 + 12 = 205

Solved Example 22:
In a certain there are four states. Each state has four major cities. All the major cities in a state are connected with each other via three different modes of transport namely rail, road and air. But a city is connected a another city via only one mode of transport if it belongs to the other states. What is the total number of different routes constructed among the major cities in the given country?
Solution:
All the routes can be classified in two categories: First - routes connecting two cities of same state and Second - routes connecting two cities of different states.
First Category: To calculate this first we can select 1 state out of 4 states in four ways then for that particular state we can select 2 cities out of four cities in 6 ways $\left( {^{\rm{4}} {\rm{C}}_{\rm{2}} } \right)$. Now we know that between these two cities 3 routes are possible. So the total number of routes of this category would be 4 x 6 x 3 = 72.
Second Category: To calculate this first we can select 2 states in 6 ways $\left( {^{\rm{4}} {\rm{C}}_{\rm{2}} } \right)$. Then every city of either state is connected with any city of the other state with one route only and there are 4 cities in either state. So the total number of routes of this category would be 6 x 4 x 4 = 96. Total number of routes = 72 + 96 = 168.

Solved Example 23:
Five intersecting straight lines are drawn in a plane. What is the minimum and maximum number of points of intersection? What is the maximum number of triangles that can be formed?
Solution:
As the lines are intersecting, so the minimum number of intersection points is 1. And maximum number of intersection points can be obtained only if we consider that every pair of two lines gives a distinct intersection point. Thus the maximum number of intersection points would be $^{\rm{5}} {\rm{C}}_{\rm{2}}$ or 10. Again, if we are to calculate the maximum number of triangles can be formed by five intersecting lines we have to consider that every group of three lines produces a distinct triangle and in that way maximum number of triangles would be $^{\rm{5}} {\rm{C}}_{\rm{3}}$ or 10

Solved Example 24:
24. 10 points are drawn in a plane such that 3 points are collinear. Then
(i) How many straight lines can be drawn by joining these points?
(ii) How many triangles can be drawn by taking these points as the verticles?
Solution:
(i) $^{{\rm{10}}} {\rm{C}}_{\rm{2}} {\rm{ - }}^{\rm{3}} {\rm{C}}_{\rm{2}}$ = 45 - 3 + 1 = 43 lines
(ii) $^{{\rm{10}}} {\rm{C}}_{\rm{3}} {\rm{ - }}^{\rm{3}} {\rm{C}}_{\rm{3}}$ = 120 - 1 = 119 triangles

Solved Example 25:
Find the number of integral solutions of the equation x + y + z = 20 where x, y, z > 0.
Solution:
If x = 1, then possible values of y & z
Are 1 & 18
2 & 17
:
:
18 & 1, So there are 18 possible values
Similarly for x = 2, there are 17 possible values
Till x = 18 you which there is duly possible values so total ways are
=> 18 + 17 + ............. 1
= $\displaystyle\frac{{18\left( {18 + 1} \right)}}{2}$ = 9 x 19 = 171