Indian Statistical Institute B.Math & B.Stat : Combinatorics

A point $P$ with coordinates $(x,y)$ is said to be good if both $x$ and $y$ are positive integers. Find the number of good points on the curve $xy=27027.$ First note that, $27027 = 3^3 \times 13 \times 11 \times 7$. Now for any good point on the curve $xy=27027$, $x$ must be of the form $3^p \times 13^q \times 11^r \times 7^s$ and $y$ must be of the form $3^{p'} \times 13^{q'} \times 11^{r'} \times 7^{s'}.$ Where $p+p'=3,q+q'=1,r+r'=1$ and $s+s'=1$ Now considers the coordinates $(3^3 \times ?, 3^0 \times ?),(3^2 \times ?, 3^1 \times ?),(3^1 \times ?, 3^2 \times ?),(3^0 \times ?, 3^3 \times ?)$ where in the place of $?$ in the $x-$ coordinate we can have any combinations of the products $13^q \times 11^r \times 7^s$ and in the place of $?$ in the $y-$ coordinate we can have any combinations of the products $13^{q'} \times 11^{r'} \times 7^{s'}$ such that $q+q'=1,r+r'=1$ and $s+s'=1.$ Note that for the equation $q+q'=1$ the possible non-negative solutions are $(1,0), (0,1)$. Similarly for the other two equations $r+r'=1$ and $s+s'=1$. Counting the combinations for $?$ is the $x-$coordinate for the coordinate $(3^3 \times ?, 3^0 \times ?)$ we can have CASE I : All the three numbers $13,11,7$ appears which can be done in $\binom {3}{3}$ ways. $?$ in the $y-$ coordinate the must contain $13^0,11^0,7^0$. CASE II : Any two of the three numbers $13,11,7$ appears which can be done in $\binom {3}{2}$ ways. $?$ in the $y-$ coordinate the must contain $13$ or $11$ or $7$. CASE III : Any one of the three numbers $13,11,7$ appears which can be done in $\binom {3}{1}$ ways. $?$ in the $y-$ coordinate the must contain $13,11$ or $11,7$ or $7,13$. CASE IV : None of the three numbers $13,11,7$ appears which can be done in $\binom {3}{0}$ ways. $?$ in the $y-$ coordinate the must contain $13,11,7$. Giving a total of $\binom {3}{3}+ \binom {3}{2}+ \binom {3}{1}+ \binom {3}{0}=8$ possibilities. Similarly we have $8$ possibilities for each of the coordinates of the form $(3^2 \times ?, 3^1 \times ?),(3^1 \times ?, 3^2 \times ?),(3^0 \times ?, 3^3 \times ?)$, giving in total $4\times8=32$ good coordinates Another problem of same flavor form $Indian- Statistical- Institute$ What is the number of ordered triplets $(a, b, c)$, where $a, b, c$ are positive integers (not necessarily distinct), such that $abc = 1000$? First note that, $1000 = 2^3 \times 5^3$. Any ordered triplet with the given condition must be of the form $(2^l\times5^m,2^p\times5^q,2^r\times5^s)$ where $l+p+r=3$ and $m+q+s=3$. Number of non-negative solutions of the above equations is $\binom {3+3-1}{2} = 10$ in both cases. Now consider one ordered triplet $(2^1\times5^m,2^0\times5^q,2^2\times5^s)$ ( 10 such triplet are possible, varying powers of 2 subjected to $l+p+r=3$ ), for this triplet now we can vary $m,q,s$ subjected to $m+q+s=3$ in 10 ways.Thus in total $10\times10=100$ ordered triplets are possible. Another good problem with a kick of $Derangement!!$ There are $8$ balls numbered $1,2,\dots,8$ and $8$ boxes numbered $1,2,\dots,8$. Find the number of ways one can put these balls in the boxes so that each box gets one ball and exactly $4$ balls go in their corresponding numbered boxes. $4$ balls can be selected in $\binom{8}{4}$ ways and for each for such selection, say $\{Ball_2,Ball_5,Ball_3,Ball_7\}$ the balls can go in their corresponding boxes in exactly one way (why?). Now the remaining $4$ balls $\{Ball_3,Ball_4,Ball_1,Ball_8\}$ has to be put in the boxes in such a way none of the balls goes to the box of same number. Since, exactly $4$ balls go in their corresponding numbered boxes. Which is nothing but $D_4$, so total number of ways is $\binom{8}{4} \times D_4$ where $D_4 = 4!\big( 1 - \frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}\big) = 9$ In general $D_n$ is Derangement of $n$ objects.