Classwork-13 Solution of Homework

Advanced Mathematics Classes Topic:Combinatorics
Dibyendu Saha Classwork-13 September 18, 2020
Solution of Homework
Homework 0.1. Prove that, Number of diagonals of a n-gon is
n(n − 3)
=
2
Solution: Using this n points number of line segment can be drawn using any two points
among them is
n n(n − 1)
= =
2 2
and among them n many are sides of the polygon. Hence, number of diagonals of a n-gon is

n n(n − 1) n(n − 3)
= −n= −n=
2 2 2
Homework 0.2. How many rectangles are there in a 8 × 8 chessboard?
Solution: In a 8 × 8 chessboard we have 9 vertical parallel lines and 9 horizontal parallel

lines. Now each of the vertical lines intersect each of the horizontal lines and a rectangle will
need 2 vertical lines intersecting with two horizontal lines. Hence, number of rectangles are

9 9
= ×
2 2
1 Some Practise Problems

Example 1.1. Suppose there are 10 points in a plane.
(i) If no 3 of them are colinear then how many straight lines are possible which passes
through them?[By ”passes through them” we mean passes through at least 2 points of
them]
Ans.: A straight will be passes through atmost two points as well , since no three
points are colinear. Hence number of st. lines passes through them

10
=
2
1
(ii) Find number of triangles possible with vertices from these 10 points.
Ans.: Since, no three points are colinear, any combination of these 10 points taking 3
at a time will produce unique triangle. Hence, number of such triangles is

10
=
3
(iii) Suppose, 4 of the 10 points are colinear and among the rest 6 no three are colinear.
Then how many straight lines are possible through these 10 points?
Ans.: If these 4 points were non-colinear, then number of straight lines possible would
be
10
=
2
But due to colinearity of the four points no different straight lines will be formed by
4

them. Hence we have to subtract 2 many straight lines which in this case actually
produces same straight line and count 1 for that straight line. hence, the number of
straight lines is
10 4
= − +1
2 2
(iv) In the same set up i.e. 4 of the 10 points are colinear and among the rest 6 no three
are colinear. Then how many triangles are possible through these 10 points?
Ans.: If these 4 points were non-colinear, then number of triangles possible would be

10
=
3
But due to colinearityof the four points no triangles will be formed by them. Hence
we have to subtract 43 from the above. Hence, number of triangle possible will be,

10 4
= −
3 3
Example 1.2. Suppose you have 5 thousand rupees notes, 4 fifty rupees notes and 3 five
rupees notes. How many donation amounts are possible?
2
Solution: Here, due to the limited number of supply of each kind of notes, we can nicely
decompose any donation amount into unique break up. For example, suppose the donation
amount is 2055 then the only possibility is to take 2 thousand rupees notes, 1 fifty rupees note
and 1 five rupee note. So any combination will contain some thousand rupees notes some
fifty rupees notes and some five rupees notes, let these numbers be x, y and z respectively.
Then clearly, number of possibilities of taking thousand rupees notes is (5+1)[take one or
take two or take three or take four or take five or do not take any] i.e. number of possible
values of x is (5+1). Similarly number of possible values of y will be (4+1) and number of
possible values of z will be (3+1). Hence total number of such amounts will be,
= (5 + 1) × (4 + 1) × (3 + 1)
Example 1.3. Find number of divisor(including 1 and 36) of 36
Solution: Prime factorisation of 36 is

36 = 22 × 32
Now any divisor of 36 will never have prime factors other than 2 and 3. Hence, any divisor
can be written as 2α × 3β . Here, number of possible value of α is (2+1) and that of β is
(2+1). Hence, number of divisors
= (2 + 1) × (2 + 1)
Example 1.4. Find number of divisor of 10800
Solution: Prime factorisation of 10800 is

10800 = 24 × 33 × 52
Now any divisor of 10800 will never have prime factors other than 2,3 and 5. Hence, any
divisor can be written as 2α × 3β × 5γ . Here, number of possible value of α is (4+1) and that
of β is (3+1) and that of γ is (2+1). Hence, number of divisors
= (4 + 1) × (3 + 1) × (2 + 1)
Generalisation:
If prime factorisation of a number n is
n = pa11 · pa22 · · · pakk
then number of divisors of n is
(a1 + 1) × (a2 + 1) × · · · × (ak + 1)
3
Example 1.5. Find sum of the divisors of the number 36.
Ans.: Any divisor of the number 36 can be written as
2α 3β
where, values of α are α = 0, 1, 2 and that of β is β = 0, 1, 2. Hence, sum of the divisors will
be,
= 20 30 + 20 31 + 20 32 + 21 30 + 21 31 + 21 32 + 22 30 + 22 31 + 22 32
= 20 (30 + 31 + 32 ) + 21 (30 + 31 + 32 ) + 22 (30 + 31 + 32 )
= (20 + 21 + 22 )(30 + 31 + 32 )
= (1 + 2 + 22 )(1 + 3 + 32 )
Generalisation: Let the prime factorisations of the numbers n be,
n = pa11 pa22 · · · pakk
Then any divisor of the number n will be of the form
pi11 pi22 · · · pikk
where,
i1 = 0, 1, 2, · · · , a1
i2 = 0, 1, 2, · · · , a2
..
.
ik = 0, 1, 2, · · · , ak
hence, sum of the divisors can be written as,

a1 X
X a2 ak
X
= ··· pi11 pi22 · · · pikk
i1 =0 i2 =0 ik =0
Xa1 Xa2 Xak
= pi11 pi22 · · · pikk
i1 =0 i2 =0 ik =0
= (1 + p1 + p1 + · · · pa11 )(1
2
+ p2 + p22 + · · · pa22 ) · · · (1 + pk + p2k + · · · pakk )

Classwork-13 Solution of Homework

Uploaded by

Copyright:

Available Formats

Classwork-13 Solution of Homework

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Classwork-13 Solution of Homework

Uploaded by

Copyright:

Available Formats

Advanced Mathematics Classes Topic:Combinatorics

Dibyendu Saha Classwork-13 September 18, 2020

Homework 0.2. How many rectangles are there in a 8 × 8 chessboard?

Solution: In a 8 × 8 chessboard we have 9 vertical parallel lines and 9 horizontal parallel

1 Some Practise Problems

Example 1.3. Find number of divisor(including 1 and 36) of 36

Solution: Prime factorisation of 36 is

Example 1.4. Find number of divisor of 10800

Solution: Prime factorisation of 10800 is

Example 1.5. Find sum of the divisors of the number 36.

Ans.: Any divisor of the number 36 can be written as

Generalisation: Let the prime factorisations of the numbers n be,

n = pa11 pa22 · · · pakk

Then any divisor of the number n will be of the form

pi11 pi22 · · · pikk

hence, sum of the divisors can be written as,

You might also like