Combinatorics, counting and number theory.

combinationscombinatoricsgcd-and-lcmnumber theorypermutations

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!

Best Answer

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.

Related Question