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.