1.1 Some Corner Cases
We’ve almost covered the essence of combinatorics that are needed at a beginner’s level to start studying this beautiful topic. This will be the last editorial of this module for those of you who’d not like to pursue any advanced studies in this chapter. There’ll be another editorial on this topic which will cover some of the important concepts required for the Olympiads and other entrances. We’ll thus end this with some specific set of problems.
Ex 1:
Find the number of rectangles that can be drawn with sides as positive integers within a square of dimensions \(n\times n\).
Solution:
Note that a square of dimensions \(n\times n\) translates to a grid of \((n+1)\times (n+1)\) points. Now essentially, it’s a mtter of choosing any 2 points in a row, followed by any 2 points in the respective columnes. Thus the total number of rectangles possible = \([C(n+1,2)]^2=\left[ \frac{n(n+1)}{2}\right]^2\).
Test Your Concepts:
How many squares of integer lengths are possible in a rectangle of dimensions \(n\times p\), with \(n<p\)?
Ex -2:
Given a set of distinct digits \(\{a_1,a_2,a_3…a_n\}\), find the sum of the digits in the units place of all the numbers that can be formed from these digits.
Solution:
We know that each of the digits will be occuring in the unit place of the numbers formed by these digits. Let’s see how many times \(a_1\) occurs in the units digit place. Fixing the last digit to be \(a_1\), there will be a total of \((n-1)!\) numbers. Similarly, we’ll have \((n-1)!\) numbers with each of \(a_2,a_3,a_4..a_n\) in the units place. Thus the sum of the units digits of all the numbers formed by the given set of digits = \((n-1)!(a_1+a_2+a_3+..a_n)\).
Test your Concepts:
Show that the sum of all n-digit numbers formed by the distinct digits \(\{a_1,a_2,…,a_n\}\) is \((n-1)!(a_1+a_2+…+a_n)\frac{(10^n-1)}{9}\).
Ex -3:
\(n\) straight lines are drawn in the plane, such that no 2 of them are parallel and no 3 of them intersect at the same point. Find the number of parts into which the plane is divided into by these lines.
Solution:
We go back to our old concepts of Recurrance relations which we studied in our Progressions and Sequences module.
Let’s assume that we define the necessary number of regions into which \(n\) lines divide our plain by the notation \(L_n\). We try to recursively derive \(L_n\) from \(L_{n-1}\). So this nth line intersects each of the old \(n-1\) lines at one point and divides each segment/region into 2. And hence, this new line adds \(n\) more regions. Also note that \(L_1=2\).
We thus have \(L_n=L_{n-1}+n\). Solving this (Please do it yourself, if you’re unable to solve, post it in the forums and we’ll help you out) we get the relation \(L_n=1+\sum\limits_{i=1}^{i=n}i\).
1.2 Legendre’s Formula – Power of a Prime
We denote the largest exponent of a prime \(p\) that is contained in \(n!\) by Legendre’s forumula, which is denoted by \(\nu_p\) and is given below:
The proof, and further reading can be found over here.
We use this forumla quite a lot, for example to find the number of trailing zeros in the factorial of a number.
Ex -4:
Find the number of trailing zeros in \(10!\).
Solution:
We’d be using Legendre’s method to find the power of 10 in 10!. So, we’d need to find the power of \(2\) and \(5\) in \(10!\). We thus have
Thus the power of 2 in 10! is 8. Now similarly for 5 we have
Thus we have the power of 10 in 10! as \(\text{min}(\nu_2,\nu_5)=2\), which means that there are 2 trailing zeros in 10!.
Test Your Concepts:
Find the maximum exponent of 12 in 12!