6
$\begingroup$

Using combinatorial argument prove that $\frac{(3n)!}{2^n\times 3^n}$ is an integer.

If we arrange $3n$ objects where there are 3 objects of one kind, another 3 objects of second kind $\cdots$ and 3 objects of $n^{th}$ kind then the number of ways are $\frac{(3n)!}{3^n}$. But I can't figure out how to introduce $2^n$ in the denominator.

  • 1
    Use group theory. The set $\{1,2,3,4,5,6,\dots,3n-2,3n-1,3n\}$ breaks up into 3-element subsets $\{1,2,3\}, \{4,5,6\},\dots,\{3n-2,3n-1,3n\}$. Let $H$ be the subgroup of $S_{3n}$ consisting of those permutations that preserve those $n$ subsets (sending $\{1,2,3\}$ to $\{1,2,3\}$, and so on). Then $H$ is a direct product of $n$ copies of $S_3$, so $\#H = 6^n$. By Lagrange, $\#H$ divides $\#S_{3n} = (3n)!$. So a combinatorial interpretation of $(3n)!/6^n$ is that it counts the number of left cosets of $H$ in $S_{3n}$. The same argument shows $(ab)!/a!^b$ is an integer for any $a, b \geq 1$.2012-11-24
  • 0
    By dividing the $3n$ people into unlabelled **teams** of $3$, you can show that in fact $(3!)^n$ divides $\dfrac{(3n)!}{n!}.$$2012-11-24

2 Answers 2

5

Your argument is really good. There is just one flaw: how did you get $\frac{(3n)!}{3^n}$ for the number of different arrangements? I think that the number of possible arrangements is a bit different, and if you figure out what it is, then the problem will be solved.

  • 0
    Could you please illustrate more?2012-11-24
  • 0
    @Amr Think about why you divided by $3^n$.2012-11-24
  • 0
    I don't see why division by $3^n$ gives a correct answer in the first place.2012-11-24
  • 0
    oh it must by divided by $3!$. That was such a stupid mistake.2012-11-24
5

Since $2^n$ and $3^n$ are always coprime, you can split up the problem into two parts:

  1. $3^n \vert (3n)!$ (You already did that yourself.)
  2. $2^n \vert (3n)!$ (But analogously to your own consideration, one immediately sees that $2^n $ divides even $(2n)!$, which is a divisor of $(3n)!$

This proves $6^n=\text{lcm}(2^n,3^n) \vert (3n)!$.