+91 9600 121 800

Plans

Dashboard

Daily & Speed

Quant

Verbal

DILR

Compete

Free Stuff

calendarBack
Quant

/

Modern Maths

/

Permutations & Combinations

Permutations And Combinations

MODULES

bookmarked
Basics of Permutations
bookmarked
Basics of Combinations
bookmarked
Letters Technique
bookmarked
Using Blanks
bookmarked
Blanks with Repetition
bookmarked
Slotting Technique
bookmarked
Conditional Permutations
bookmarked
Special Types
bookmarked
Circular Permutations
bookmarked
Derangement
bookmarked
Binomial Expansion
bookmarked
Forming Groups
bookmarked
Identical Elements
bookmarked
Identical Groups
bookmarked
Selection in Geometry
bookmarked
Past Questions

CONCEPTS & CHEATSHEET

Concept Revision Video

SPEED CONCEPTS

Permutations & Combinations 1
-/10
Permutations & Combinations 2
-/10
Permutations & Combinations 3
-/10
Permutations & Combinations 4
-/10
Permutations & Combinations 5
-/10
Permutations & Combinations 6
-/10

PRACTICE

Permutations & Combinations : Level 1
Permutations & Combinations : Level 2
Permutations & Combinations : Level 3
ALL MODULES

CAT 2025 Lesson : Permutations & Combinations - Selection in Geometry

bookmarked

7. Combinations in Geometry

7.1 Intersection of circles of different radii

Number of ways in which 222 circles can be selected from nnn circles === nC2=n(n−1)2^{n}C_{2} = \dfrac{n(n - 1)}{2}nC2​=2n(n−1)​

As any 222 circles can form a maximum of 222 intersection points,

Maximum Intersection points =n(n−1)2×2=n(n−1)= \dfrac{n(n - 1)}{2} \times 2 = \bm{n(n - 1)}=2n(n−1)​×2=n(n−1)

7.2 Intersection of non-concurrent lines

When 333 or more lines intersect each other at the same common point, they are called concurrent lines.

If there are n\bm{n}n non-concurrent lines, any 222 such lines will form 111 intersection point. Number of intersection points is the number of ways in which 222 lines can be selected, i.e. nC2\bm{^{n}C_{2}}nC2​.

7.3 Lines drawn through non-collinear points

Non-collinear points are those where not more that 222 of them can lie on a straight line. In other words, three or more points do not lie on one line.

Through any 222 points, 111 line can be drawn. Therefore, to find number of lines formed by a pair of points, we need to find the number of pairs that can be chosen from n\bm{n}n non-collinear points, i.e. nC2^{n}C_{2}nC2​.

7.3.1 Lines drawn through collinear & non-collinear points

Note that the collinear cases need to be removed. So, number of straight lines that can be drawn where there are nnn points of which rrr are collinear is nC2−^{n}C_{2} -nC2​− rC2+1^{r}C_{2} + 1rC2​+1. Note that 111 is added back as this is to consider the 111 line that can be drawn through the collinear points.

Example 56

A to J are 101010 points on a plane. A, B, C and D are collinear. E, F and G are another set of collinear points. If no other set of 333 or more points are collinear, then how many different lines can be drawn through these points?

Solution

For a line to be formed, two distinct points are required. So, the total number of lines which can be formed with the 101010 points are 10C2=45^{10}C_{2} = 4510C2​=45 lines.

But since A, B, C and D are collinear, we can construct only one line with it. So, the 4C2^{4}C_{2}4C2​ lines formed with it has to be eliminated and only 111 line should be added. Likewise, 3C2^{3}C_{2}3C2​ lines has to be eliminated and only 111 line should be added for E, F and G, as they are also collinear.

Therefore, total number of lines === 10C2−^{10}C_{2} -10C2​− 4C2+1−^{4}C_{2} + 1 -4C2​+1− 3C2+1=^{3}C_{2} + 1 =3C2​+1= 45−6+1−3+1=3845 - 6 + 1 - 3 + 1 = 3845−6+1−3+1=38

Answer: 383838


Example 57

What is the maximum number points of intersection that can be formed by 6 non-overlapping lines and 5 circles of different radii on a plane?

Solution

2 non-overlapping lines can intersect at a maximum of 1 point. 2 circles of different radii can intersect at a maximum of 2 points. 1 circle and 1 line can intersect at a maximum of 2 points.

Selecting No. of Ways Max Intersection Points Total Points
222 lines 6C2^{6}C_{2}6C2​ 111 15×1=1515 \times 1 = 1515×1=15
222 circles 5C2^{5}C_{2}5C2​ 222 10×2=2010 \times 2 = 2010×2=20
111 line & 111 circle 6C1×^{6}C_{1} \times6C1​× 5C1^{5}C_{1}5C1​ 222 30×2=6030 \times 2 = 6030×2=60
Total 959595


Answer: 959595


7.4 Triangles drawn through non-collinear points

As the points are non-collinear, with every 333 points, 111 triangle can be drawn. Therefore, number of triangles that can be drawn is the number of ways in which 333 points can be selected from n\bm{n}n non-collinear points, which is nC3\bm{^{n}C_{3}}nC3​.

7.4.1 Triangles drawn through collinear & non-collinear points

If 333 points lie on a straight line, we cannot draw a triangle using them. Let out of a total of n\bm{n}n points, r\bm{r}r points be lying on a straight line, and none of the other points being collinear.

Total number of triangles, assuming all nnn points are collinear === nC3^{n}C_{3}nC3​

However, the above calculation includes triangles formed using the rrr collinear points, which is rC3\bm{^{r}C_{3}}rC3​. This needs to be subtracted.

Therefore, number of triangles that can be drawn from n\bm{n}n given points, where r\bm{r}r points lie on the straight line and none of the other points are collinear === nC3−rC3\bm{^{n}C_{3} - ^{r}C_{3}}nC3​−rC3​

Example 58

There are 151515 points on a plane. Of this, 666 of them belong to one set of collinear points and 444 of them are another set of collinear points. The rest of the points are non-collinear. What is the maximum number of triangles that can be formed using these points as the vertices?

Solution

If all 999 points were non-collinear, then number of triangles that can be drawn === 15C3=455^{15}C_{3} = \bm{455}15C3​=455

Triangles that cannot be formed are those within the respective sets of collinear points.

Triangles that cannot be formed === 6C3+^{6}C_{3} +6C3​+ 4C3=24^{4}C_{3} = \bm{24}4C3​=24

Number of triangles that can be formed =455−24=431= 455 - 24 = \bm{431}=455−24=431

Answer: 431431431


7.5 Diagonals of a Polygon

This can be explained in 222 ways.

Logical Approach: From a vertex of a polygon, diagonals can be drawn to all the other vertices other than itself and its 222 adjacent vertices. Therefore, in an nnn-sided polygon, from a point we can draw n−3\bm{n - 3}n−3 diagonals. There are nnn such vertices we should be able to draw n(n−3)n(n - 3)n(n−3) diagonals. However, diagonals are double counted here (for instance a diagonal from A to C which is also from C to A is counted twice). We can remove this by dividing by 222.

Number of diagonals of an nnn-sided polygon =n(n−3)2= \bm{\dfrac{n(n - 3)}{2}}=2n(n−3)​

Combinations Approach: Between any 222 points in a polygon, lines can be drawn. Number of ways in which we can select 222 points is nC2=n(n−1)2^{n}C_{2} = \dfrac{n(n - 1)}{2}nC2​=2n(n−1)​

However, lines connecting adjacent vertices are sides of the polygon and not diagonals. There are nnn such sides which need to be removed.

Number of diagonals of an nnn-sided polygon === nC2−n=n(n−1)2−n=^{n}C_{2} - n = \dfrac{n(n - 1)}{2} - n =nC2​−n=2n(n−1)​−n= n(n−3)2\bm{\dfrac{n(n - 3)}{2}}2n(n−3)​

7.6 Parallelograms formed by parallel lines

Where m\bm{m}m parallel lines intersect another set of n\bm{n}n parallel lines, parallelograms can be formed. We can form a parallelogram with any 222 of the mmm parallel lines and any 222 of the nnn parallel lines.

mC2^{m}C_{2}mC2​ and nC2^{n}C_{2}nC2​ is the number of ways to select 222 lines from mmm and nnn parallel lines respectively.

Number of parallelograms that can be formed === mC2×\bm{^{m}C_{2}} \timesmC2​× nC2\bm{^{n}C_{2}}nC2​

7.7 Rectangles and Squares

From a larger rectangle with mmm rows and nnn columns,
Number of rectangles that can be formed =(1+2+...+m)= (1 + 2 + ... + m)=(1+2+...+m) (1+2+...+n)=(1 + 2 + ... + n) =(1+2+...+n)= m(m+1)2×n(n+1)2\dfrac{m (m + 1)}{2} \times \dfrac{n (n + 1)}{2}2m(m+1)​×2n(n+1)​

Number of squares that can be formed =mn+(m−1)(n−1)+(m−2)(n−2)+...= \bm{mn + (m - 1) (n - 1) + (m - 2) (n - 2) + ...}=mn+(m−1)(n−1)+(m−2)(n−2)+...

If we have a square instead of a rectangle, then the number of rows and columns will be the same. We can simply replace mmm with nnn in the above formulae.

From a larger square with nnn rows and nnn columns,

Number of rectangles that can be formed =(n(n+1)2)2= \bm{\left( \dfrac{n(n + 1)}{2} \right)^{2}}=(2n(n+1)​)2

Number of squares that can be formed =n2+(n−1)2+...+1== n^{2} + (n - 1)^{2} + ... + 1 ==n2+(n−1)2+...+1= n(n+1)(2n+1)6\bm{\dfrac{n (n + 1) (2n + 1)}{6}}6n(n+1)(2n+1)​

Example 59

How many squares are there in a chessboard which has 888 rows and 888 columns?

Solution

With equal number of rows and columns, we have a large square.

Number of squares that can be formed from a large square =n(n+1)(2n+1)6= \dfrac{n(n + 1) (2n + 1)}{6}=6n(n+1)(2n+1)​

=8(8+1)(16+1)6=12×17=204= \dfrac{8 (8 + 1) (16 + 1)}{6} = 12 \times 17 = 204=68(8+1)(16+1)​=12×17=204

Answer: 204204204


Loading...Loading Video....