Concepts of Permutations and Combination is applied across a lot of chapters and questions are frequently asked in CAT, XAT, NMAT, etc every year. It remains crucial when you start implementing the concepts in various fields and applications making you a better decision maker.
Basic understanding of algebra, numbers and geometry will help you understand, comprehend and solve questions from this chapter.
Algebraic Properties
[Click Here for Previous Year CAT Questions]
-
For a natural number n, the given equation is x1 +x2 +x3 +…+xn =n
- If xi ≥0, the number of integral solutions is n + r −1Cr −1
- If xi ≥1, the number of integral solutions is n −1Cr −1
- If m ≤ xi ≤ k, the number integral solutions is coefficient of xn in the expansion of (xm +xm+1 +……+xk )r
- If a ≤x ≤b,a ≤x ≤b,...,a ≤x ≤b the number of integral solutions is coefficient of xn in (xa1 +xa1 +1 +….+xb1 )(xa2 +xa2 +1 +...+xb2 )... (xar +xar +1 +….+xbr )
-
For a natural number n, if the given inequation is x1 +x2 +x3 +...+xr ≤ n.
Then, add a dummy variable xr + 1 in the given equation, so that inequality can be converted into equality before finding the number of solutions.
- If xi ≥ 0, the number of integral solutions to x +x +x +..+x ≤n is same as the number of integral solutions of x1 +x2 +x3 +...+xr +xr+1 =n.
Thus the required number of integral solutions is n+ r Cr .
-
For a natural number n, number of solutions of | x1 | + | x2 | + . . . + | xm | = n.
- The total number of integral solutions of | a| + | b| = n is 4n
- The total number of integral solutions of |a|+|b|+|c|=n is 4n2 +2
- The total number of integral solutions of |a|+|b|+|c|+|d| =n is \(\frac{8n}{3} (n^2+2)\)
-
For a natural number n, number of terms of binomial and multinomial expressions.
- Total number of terms in (x + y)n = n +1
- Total number of terms in (a1 +a2 +….+an)m =m+n−1Cn−1
- Total number of terms in (1+ x + x2 +…..+xn )m is x1 + x2 + x3 +...≤ n x1 +x2 +x3 +x4 =n
can be expressed as so the required number of integral solutions is n + 3C3.
Number Properties
[Click Here for Previous Year CAT Questions]
If N is a natural number where
N = a p bq cr ...., whereas a, b, c,…are distinct prime numbers.
- Total number of factors of a composite number = ( p +1)(q +1)(r +1)……
- Sum of factors of a composite number = \(\frac{a^{p+1}-1}{a-1} \times\frac{b^{q+1}-1}{b-1} \times \frac{c^{r+1}-1}{c-1} \times.....\)
- Product of factors of a composite number =N1/2 (total number of factors of N)
- Total number of odd factors of a composite number = ( p +1)(q +1)(r +1); where each of p, q, r… must be odd prime number only
if N = 2k a p bq cr ...., then eliminate 2k from the factors of N to obtain number of odd factors of N .
- Total number of even factors of a composite number = Total number of factors of N − Total number of odd factors.
- Total number of co-primes to N , which are less than
N= N \((1-\frac{1}{a}) (1-\frac{1}{b}) (1-\frac{1}{c}) ......\)
- Sum of all the co-primes of N which are less than N = (N/2). Number of co-primes to N which are less than N.
- Total number of ways in which N can be written as a product of two co-primes =2n −1; where n is the number of distinct prime factors of N .
- Total number of ways in which N can be expressed as a product of two factors = \(\frac{Total \ number \ of factors\ of\ N}{2}\)
- Total number of ordered pairs (x, y) such that LCM of x and yis a composite number = (2p +1)(2q +1)(2r +1)…
Geometrical Properties
[Click Here for Previous Year CAT Questions]
(i) If there N number of points of which no three points are collinear
(a) The number of straight lines that can be formed by joining them = nC2
(b) The number of triangles that can be formed by joining them = nC3
(c) The number of quadrilaterals that can be formed by joining them = nC4
(d) The number of polygons with k sides that can be formed by joining them= nCk
(e) The number of diagonals in a polygon of n sides = nC2 −n
(ii) In a plane if there are n points out of which m points are collinear, then
(a) The number of straight lines that can be formed by joining them = nC2 − mC2 +1
(b) The number of triangles that can be formed by joining them = n C − mC 33
(c) The number of polygons with k sides that can be formed by joining them = nCk − mCk
(iii) If n points are given on the circumference of the circle, then
(a) The number of straight lines that can be formed by joining them = nC2
(b) The number of triangles that can be formed by joining them = nC3
(c) The number of quadrilaterals that can be formed by joining them = nC4
(d) The number of polygons with k sides that can be formed by joining them = nCk
(e) The number of diagonals in a polygon of n-sides = nC2 −n
(iv) The number of regions in which a line/plane/space/ sphere can be divided by n points/lines/circles/ ellipses
(a) If n straight lines are drawn in the plane such that no two lines are parallel and no three lines are concurrent, then the maximum number of parts/regions into which these lines divide the plane is
nC0 +nC1 + nC2 = \(\frac{n (n+1)}{2}+ 1\)
(b) If n straight lines are intersecting a circle such that no two lines are parallel and no three lines are concurrent, the maximum number of parts/regions into which these lines divide the circle is
nC0+nC1+nC2 = \(\frac{n(n+1)}{2}+ 1\)
(c) If n points lie on the circumference of a circle and are connected by straight lines intersecting the circle such that no three lines are concurrent (that is no three lines ever pass through the same point), then the maximum number of parts/regions into which these lines divide the circle is nC0 +nC2 +nC4..
(d) If n points are given on the circumference of a circle and the chords determined by them are drawn. If no three chords have a common point, number of triangles all of whose vertices lie inside the circle
(e) If n circles are drawn in the plane such that no two of them are tangent, none of them lies entirely within or outside of another one and no three of them are concurrent, the maximum number of parts/regions into which these circles divide the plane is n(n−1)+2
(f) If n ellipses are drawn in the plane such that no two of them are tangent, none of them lies entirely within or outside of another one and no three of them are concurrent, the maximum number of parts/regions into which these ellipses divide the plane is 2n(n − 1) + 2
(g) If there are n overlapping triangles, the maximum number of regions into which these triangles divide the plane is 3n2 −3n+2
(h) If n planes are drawn in the space such that no four planes intersect at a single point and the intersection of any three planes are non-parallel lines and no two planes are parallel, the maximum number of spacial regions into which these planes divide the space is nC0+ C1+ C2+ C3
(i) The maximum number of regions into which a 3-dimensional cube/sphere/cylinder can be partitioned by exactly n planes is nC0 +nC1 +nC2 +nC3
(j) If n circles are intersecting each other, maximum number of points of intersection = 2×(nC2)=nP2 =n(n−1)
Previous year CAT Questions
Ques 1: The side of an equilateral triangle is 10 cm long. By drawing parallels to all its sides, the distance between any two parallel lines being the same. The triangle is divided into smaller equilateral triangle, each of which has sides of length 1 cm. How many such small triangles are formed? (CAT 2012)
- 60
- 90
- 120
- None of these
Click Here for the Answer
Ans: (D)
As the no of triangles in the row 1 from the top is 1, Row 2 is 3 and row 3 is 5.
So, the number of triangles in nth row is (2n-1)
Total number is n2 i.e., the sum of 1st n odd numbers = n2
Total number of triangles is. n = 102 =100
Ques 2: An intelligence agency forms a code of two distinct digits selected from 0, 1, 2, ..., 9 such that the first digit of the code is non-zero. The code, handwritten on a slip, can however potentially create confusion, when read upside down-for example, the code 91 may appear as 16. How many codes are there for which no such confusion can arise? (CAT 2003)
- 80
- 78
- 71
- 69
Click Here for the Answer
Ans: (D)
The numerals available are 0, 1, 2,..., 9. The first digit can be entered in 9 different ways (0 is unacceptable), and the second digit can be entered in 9 different ways (digit repetition is not permitted).
Thus, the code can be generated in 9 x 9 = 81 distinct ways.
There are now only four numerals that can cause confusion: 1, 6, 8, and 9. The same can also be expressed in the following methods.
Number of ways confusion can arise = 4 x 3 = 12
Answer to the question = 81 – 12 = 69
Ques 3: How many numbers can be made with digits 0, 7, 8 which are greater than 0 and less than a million? (CAT 2002)
- 496
- 486
- 1084
- 728
Click Here for the Answer
Ans: (D)
No of ways for selecting single digit = 2
No of ways for selecting two digit=2×3=6
No of ways for selecting three digits= 2 × 3 × 3 = 18
No of ways for selecting four digits= 2 × 3 × 3 × 3 = 54
No of ways for selecting five digits= 2 × 3 × 3 × 3 × 3 = 162
No of ways for selecting six digits= 2 × 3 × 3 × 3 × 3 × 3 = 486
total number of ways= (2 + 6 + 18 + 54 + 162 + 486) = 728
Ques 4: In how many ways is it possible to choose a white square and a black square on a chess-board, so that the squares must not lie in the same row or column? (CAT 2002)
- 56
- 896
- 60
- 768
Click Here for the Answer
Ans: (D)
the number of ways in choosing one white and one black square on the chess =32C1 × 32C1 =32 x×32 =1024
Number of ways in which square lies in the same row
(white square = 4, black square = 4, Number of rows = 8) = 4C1 × 4C1 × 8 = 128
∴Number of ways in which square lie on the same column = 4C1 × 4C1 ×8 =128
Total number in which square lie on the same ow or same column = 128 + 128 = 256
required number of ways = 1024 − 256 = 768.
Answer the questions based on the following information. (5-6)
Ques 5: Each of the 11 letters A, H , I , M , O , T ,U , V , W , X and Z appears same when looked at in a mirror. They are called symmetric letters. Other letters in the alphabet are asymmetric letters. How many four-letter computer passwords can be formed using only the symmetric letters (no repetition allowed)? (CAT 2002)
- 7920
- 330
- 146.4
- 419430
Click Here for the Answer
Ans: (A)
Ist place can be filled in 11 ways.
IInd place can be filled in 10 ways.
IIIrd place can be filled in 9 ways.
IVth place can be filled in 8 ways.
Hence, required number of ways =11 x ×10 x ×9 x×8 = 7920 ways
Ques 6: How many three-letter computer passwords can be formed (no repetition allowed) with at least one symmetric letter?
- 990
- 2730
- 12870
- 1560000
Click Here for the Answer
Ans: (C)
Three letter password from 26 letters can be selected in 26 x× 25 x× 24 ways.
Three letter password from 15 asymmetric letters can be selected in 15 x×14 x×13ways.
Therefore, three letter password with at least one symmetric letter can be made in
(26 × 25 × 24) − (15 × 14 × 13) = 12870 ways.
Ques 7: The figure below shows the network connecting cities A, B, C, D, E and F. The arrows indicate permissible direction of travel. What is the number of distinct paths from A to F? (CAT 2001 )
- 9
- 10
- 11
- None of these
Click Here for the Answer
Ans: (B)
All the routes from A to F are given here under : ABDF , ACEF, ABF, ABEF, ACDF , BCDEF , ACDEF, ABDEF, ABCDF, ABCEF.
Ques 8: For a scholarship, at the most n candidates out of 2n + 1 can be selected. If the number of different ways of selection of at least one candidate is 63, the maximum number of candidates that can be selected for the scholarship is (CAT 1999)
- 3
- 4
- 6
- 5
Click Here for the Answer
Ans: (A)
No of candidates can be selected in (2n + 1 − 1) ways, out of (2n + 1) at least one candidate will be selected.
(2n + 1 − 1) = 63
2n + 1 =64 = 26
n = 2.5 \( \approx\) 3
Qies 9: Ten points are marked on a straight line and 11 points are marked on another straight line. How many triangles can be constructed with vertices from among the above points? (CAT 1999)
- 495
- 550
- 1045
- 2475
Click Here for the Answer
Ans: (C)
Required number of triangles = 10C2 × 11 + 11C2 × 10 = 45 x 11 + 55 x 10 =1045
Ques 10: How many numbers can be formed from 1, 2, 3, 4, 5 (without repetition), when the digit at the unit’s place must be greater than that in the ten’s place? (CAT 1998)
- 54
- 60
- \(\frac{51}{3}\)
- 2 × 4!
Click Here for the Answer
Ans: (B)
The unit is place digit must be greater than the ten's place digit.
Consequently, if the digit 5 occupies the unit place, the remaining four digits do not need to be in any particular order, so required numbers = 4!.
if the numeral 4 occupies the unit position, the digit 5 cannot occupy the tens' positions. Therefore, the numerals in the tens location will be 1, 2, or 3. This can occur in three ways.
The remaining three numerals can be placed in the last three positions in three! different methods. Thus, we have (3 x 3!) numerals ending in 4 in total.
Similarly, if we have 3 in the unit is place, we can position either 1 or 2 in the ten's place. This can occur in two ways.
The remaining three numerals can be placed in the last three positions in three! different methods. Consequently, there will be (2 x 3!) numerals ending in 3. Likewise, we can determine that there will be three numbers ending in 2 and none ending in 1. Consequently, the sum of all numbers
4! + (3) × 3! + (2 × 3!) + 3!
=4! + 6×3!=24+ (6 ×6)=60
Ques 11: Five-digit numbers are formed using only 0, 1, 2, 3, 4 exactly once. What is the difference between the greatest and smallest numbers that can be formed? (CAT 1998)
- 19800
- 32976
- 41976
- None of these
Click Here for the Answer
Ans: (B)
Greatest five digit number is 43210 and smallest five digit number is 10234.
Hence, difference = 43210 − 10234 = 32976
Ques 12: In how many ways can eight directors, Vice-chairman and Chairman of a firm be seated at a round table, if the Chairman has to sit between the Vice-chairman and a Director? (CAT 1997)
- 9!× 2
- 2 x 8!
- 2 × 7!
- None of these
Click Here for the Answer
Ans: (B)
Consider the Vice-chairman and Chairman to be a single entity.
Now, there are 8! methods to arrange nine people around a circular table.
Vice-chairman and Chairman can be organized in two distinct methods.
Therefore, the necessary number of methods = 2 x 8!
Ques 13: A man has 9 friends : 4 boys and 5 girls. In how many ways can he invite them, if there have to be exactly 3 girls in the invites? (CAT 1996)
- 320
- 160
- 80
- 200
Click Here for the Answer
Ans: (B)
3 girls can be selected out of 5 girls in 5C3 ways.
As the number of boys to be invited is not given, hence out of 4 boys, he can invite them (2)4 ways.
Required ways = 5C3 x (2)4 = 10 x 16 = 160
Ques 14: Boxes numbered 1, 2, 3, 4 and 5 are kept in a row and they which are to be filled with either a red or a blue ball, such that no two adjacent boxes can be filled with blue balls. Then, how many different arrangements are possible, given that all balls of a given colour are exactly identical in all respects? (CAT 1995)
- 8
- 10
- 15
- 22
Click Here for the Answer
Ans: (D)
Total number of ways to fill the five boxes named 1, 2, 3, 4, and 5 with either blue or red 5 balls = 25 = 32. There are four ways to get two blue boxes next to each other. They are (12), (23), (34), and (45).
There are three ways to get blue in three boxes next to each other. They are (123), (234) and (345).
There are two ways to get four blue boxes next to each other, which are 1234 and 2345.
There is only one way to get five blue boxes. So, the number of ways to fill the boxes so that blue is in each box next to it is (4 + 3 + 2 + 1) = 10
So, the number of ways to fill the boxes so that no two boxes next to each other have blue in them is 32 - 10 = 22.
Ques 15: A, B, C and D are four towns, any three of which are non-collinear. Then, the number of ways to construct three roads each joining a pair of towns, so that the roads do not form a triangle is (CAT 1995)
- \(\frac{1}{12}\)
- \(\frac{1}{6}\)
- \(\frac{1}{4}\)
- None of these
Click Here for the Answer
Ans: (D)
There are 24 ways to choose three towns out of four to build two roads i.e., (4x3x2).
Now, a triangle is made if the third road goes from the third town to the first town, but not if it goes to the fourth town.
So, there are 24 ways to make a triangle and 24 ways to stay away from making one.
How to approach Application of Permutation and Combination questions in CAT
- Basic algebra , Number system and geometric properties understanding is required to attempt questions from this chapter.
- Practicing logical reasoning questions will help develop logic to solve questions of this chapter.
- There may be possibility to solve a question is multiple ways. Try your own comfortable way to solve for anwers.
Comments