Find the number of ordered triplets $x,y,z$

combinatoricselementary-number-theory

Find the number of ordered triplets $(x,y,z)$ of positive integers less than $13$ such that the product $x\cdot y\cdot z$ is divisible by $20$.

My work:

The possible values of $x\cdot y\cdot z$ are $20,40,60,80,100,120,140,160$. I began to make cases. I made cases for the product to be equal to $20$. I got $27$ cases.

Then for the product to be equal to $40$, I got $36$ cases.

I see that the number of cases are getting bigger. I don't know the best method of doing these types of questions.

Any help is greatly appreciated.

EDIT

Can we do it by the inclusion-exclusion principle$?$ Like counting all the triplets whose product does not divide both $5$ and $4$.

Here, $x,y,z$ have to be different as if it's not the case then the possible number of triplets exceed $216$.

Best Answer

Here is a generating function approach. We consider the set of integers $\{1,2,3,\ldots,12\}$ and mark the occurrence of prime factors $2$ and $5$ according to their multiplicity with $z$ resp. $w$. We obtain \begin{align*} \begin{array}{cccccccccccc} 1&2&3&4&5&6&7&8&9&10&11&12\\ 1&\color{blue}{z}&1&\color{blue}{z^2}&\color{blue}{w}&\color{blue}{z}&1&\color{blue}{z^3}&1&\color{blue}{zw}&1&\color{blue}{z^2}\\ \end{array}\tag{1} \end{align*} We obtain from (1) the generating function $A(z,w)$ as \begin{align*} \color{blue}{A(z,w)=5+\left(2z+2z^2+z^3\right)+(1+z)w}\tag{2} \end{align*} Since we want to count \begin{align*} |\{(x,y,z)\,:\,1\leq x,y,z\leq 12, 20|xyz\}| \end{align*} we calculate $A(z,w)^3$ which corresponds to the sum of products $x\cdot y\cdot z$ with $1\leq x,y,z\leq 12$ and count all terms which contain $z^2w$. These are the terms which correspond to a multiple of $20$.

Denoting with $[z^n]$ the coefficient of $z^n$ of a series we obtain \begin{align*} \color{blue}{\sum_{k\geq 2}}&\color{blue}{\sum_{l\geq 1}[z^k][w^l]A(z,w)^3}\\ &=\sum_{k\geq 2}\sum_{l\geq 1}[z^k][w^l]\left(5+\left(2z+2z^2+z^3\right)+(1+z)w\right)^3\tag{3.1}\\ &=\sum_{k\geq 2}[z^k]\left((1+z)^3+3\cdot 5(1+z)+3\cdot 5(1+z)^2\right.\\ &\qquad\quad+3\left(2z+2z^2+z^3\right)^2(1+z)\\ &\qquad\quad+3\left(2z+2z^2+z^3\right)\left(1+z\right)^2\\ &\qquad\quad+\left.6\cdot 5\left(2z+2z^2+z^3\right)(1+z)\right)\tag{3.2}\\ &=\sum_{k\geq 2}[z^k]\left(\left(3z^2+z^3\right)+3\cdot 5\cdot 0+3\cdot 5z^2\right.\\ &\qquad\quad+3(5)^2(2)\\ &\qquad\quad+3\left(\left(2z^2+z^3\right)+2\left(2z^2+2z^3+z^4\right)+\left(2z^3+2z^4+z^5\right)\right)\\ &\qquad\quad\left.+6\cdot 5\left(2z+2z^2+z^3\right)(1+z)\right)\tag{3.3}\\ &=4+0+15+150+3\left(3+2\cdot 5+5\right)+6\cdot 5\left(3+5\right)\tag{3.4}\\ &\,\,\color{blue}{=463} \end{align*} in accordance with other answers.

Comment:

  • In (3.1) we consider a trinomial expansion \begin{align*} (a+b+c)^3&=a^3+b^3+c^3+3\left(a^2b+a^2c+ab^2+ac^2+b^2c+bc^2\right)\\ &\qquad+6abc \end{align*}

  • In (3.2) we select all terms which contains a factor $w$, i.e. which contains a factor $c$ in the expansion from $(a+b+c)^3$.

  • In (3.3) we simplify terms by skipping constant and linear terms in $z$ and by counting some of the terms which contain a factor $z^k$ with $k\geq 2$.

  • In (3.4) we simplify further until we finally derive the result.

Related Question