Combinatorics, counting and number theory.

Question

Find number of ordered quadruples (a,b,c,d) [of positive integers] such that $lcm[a,b,c]= lcm[a,b,d]= lcm[a,c,d]= lcm[b,c,d] = 2^r\cdot3^s$

So i approached it like two of a,b,c,d has max power of 2 = r. For rest two, they have r+1 choices each. So it would be $\binom{4}{2} \cdot (r+1)^2$. Same for the power of three.

So as per me answer should be $(\binom{4}{2} \cdot (r+1) \cdot (s+1))^2$ but the answer to this problem is not given in my book.

I would really appreciate if you could tell whether my answer is correct and whether this is the correct approach and if it is not correct approach, then why?

Thanks!

Answer 1

Your approach seems alright but the way you are counting, you will have many duplicates and end up overcounting. We can count each case separately and add.

Let's take $\displaystyle 2^r$ first

Case 1 - two of them have power of $r$ and other two have power of $0 \leq p \lt r$.

Number of ways = ${4 \choose 2} \times r \times r$

Case 2 - three of them have power of $r$ and one has power of $0 \leq p \lt r$.

Number of ways = ${4 \choose 1} \times r$

Case 3 - all of them have power of $r$ for $2$. There is only $1$ way.

That gives total number of ways $ = 6r^2 + 4r + 1$

We similarly find for $s$ and then multiply for all possible quadruples.

Answer 2

It seems you have double counting. If $2^r|a,b,c$ then you count that case three times more than it should. (When you choose $a,b$ from the ${4\choose 2}$ options and choose power of $2$ of $c = r$ as one of the $r+1$ cases, that is the same as choosing $a,c$ from the ${4\choose 2}$ options and choosing the power of $2$ of $b = r$ as one of the $r+1$ cases.

I'd do it by cases If exactly $2$ of $a,b,c,d$ have power of $2=r$ and the other two powers of $2$ are not $r$ there are ${4\choose 2}r^2$. If exactly $3$ have $r$ there are ${4\choose 3}r$ and if all $4$ have $r$ there are ${4\choose 4}$.

So there are $6r^2 + 4r + 1$ ways to allocate the powers of $2$.

And there are $6s^2 + 4s + 1$ ways to allocate the powers of $3$.

So $(6r^2 + 4r + 1)(6s^2 + 4s + 1)$.

Someone might want to check my reasoning.

Answer 3

For power of $2$, consider the complement: how many ways are there at most one of $a,b,c,d$ has power $r+1$? That's $(r+1)^4 - r^4-{4 \choose 1} r^3=6r^2+4r+1$.

The total number of ways is then $(6r^2+4r+1)(6s^2+4s+1).$