Divisibility factorial

Prove that $\cfrac { (3n)! }{ { (3!) }^{ n } }$ is integer for all $n\ge 0$.

This is the solution I tried

${(3!)}^{ n }={(6) }^{ n }$.We have to prove ${(6) }^{ n }|(3n)!$.We have product of 3 consecutive numbers is divisible by $6$.Now there are $n$ pairs of $3$ consecutive numbers.Therefore ${ 6 }^{ n }y=(3n)!$ for some $y$..Therefore $\cfrac { (3n)! }{ { (3!) }^{ n } }$ is integer for all $n\ge 0$.

Is it correct?

Note by Shivamani Patil
5 years, 9 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

Using some combinatorics:

(3n)! / (3!)^n = (3n)! / (3!)(3!) ... (3!)(3!) n factors of (3!). One can think of this as the number of identical permutations with 3n letters and n different letters with 3 as frequency in the letter. It remains to prove that the number of identical permutations is an integer.

- 5 years, 9 months ago

Your solution is great.But can you give elementary number theory proof.

- 5 years, 9 months ago

The given expression can be written as $\dfrac{(3n)!}{6^{n}}$ which can be written as $\dfrac{(3n)!}{3^{n}\times2^{n}}.$Now,we have that the maximum power of $3$ that divides $(3n!)$$=\lfloor{\dfrac{3n}{3}}\rfloor+\lfloor{\dfrac{3n}{9}}\rfloor+...$Similarly the maximum power of $2$ that divides $3n!$=$\lfloor{\dfrac{3n}{2}}\rfloor+\lfloor{\dfrac{3n}{4}}\rfloor+.....$Now,for$n\geq3$ the expressions above are $>3^{n}$ and $2^{n}$ respectively.Thu for all$n\geq3$ the given expression is an integer.Checking cases for $n=0,1,2$ reveals that the given expression is an integer for all three.Hence proved.

- 5 years, 9 months ago

There are $n(3n-1)!$ pairs of 3 consecutive numbers.

How did get this? Since there are $3n$ numbers being multiplied, there should be $\frac{3n}{3} = n$ pairs of consecutive number. For example, $6! =(6*5*4)(3*2*1)$ can be partitioned into 2 pairs.

- 5 years, 9 months ago

But we have to take $(3n)!$ numbers in pairs of 3 .Therefore dividing by 3 we get $n(3n-1)!$ pairs.

- 5 years, 9 months ago

$(3n)!$ is the product of $3n$ numbers,i.e $1*2*...*(3n-1)*(3n)$. Not $(3n)!$ numbers. Also, you can check smaller cases. The highest power of $6$ dividing $(3*2)!$ is $6^2$, not $6^{2(5!)} = 6^{240}$.

- 5 years, 9 months ago

Ohh yes I missed it in hurry .I have updated solution now is it correct?

- 5 years, 9 months ago

Yes, now it is, though you could also mention the fact that the product of 3 consecutive integers is also divisible by 6.

- 5 years, 9 months ago

I have mentioned that na.

- 5 years, 9 months ago

- 5 years, 9 months ago

That's ok. u study in which class?

- 5 years, 9 months ago

11th.

- 5 years, 9 months ago

Ohhh

- 5 years, 9 months ago

(3!)^n=3^n×2^n.now 3n> 3 (n-1)> 3 (n-2)......> 3 so 3n×3 (n-1)×3 (n-2).........×3=3^n×n! contains in (3n)!.again 3n> 2n> 2 (n-1).......> 2 so 2n×2 (n-1)......×2=2^n×n! contains in (3n)!.so (3n)! is is divisible by (3!)^n

- 5 years, 9 months ago

Try formatting your maths so it's easier to read - I know it's tricky so I'll give you a few pointers. For (3)!^n place curly brackets around the n (i.e. {n} ), then place normal brackets around the whole expression, before putting a '\' before you 1st and last bracket - $...$. This should give $(3!)^{n}$. Also, (3n)! = 3n(3n-1)(3n-2)...2*1 as it is inside the brackets, rather than outside.

- 5 years, 9 months ago

Note that $\dfrac{(3n)!}{(3!)^n}$ represents the number of ways to arrange $3n$ objects with $n$ triplets of object being identical, in a row. For instance, at $n = 2$ , you are actually arranging 6 objects with 2 triplets, such as arranging AAABBB in a row, yielding $\dfrac{6!}{3!3!} = \dfrac{(2(3))!}{(3!)^2}$

Note that the number of objects = number of objects limited by the requirement of the permutation. (That is from the previous example, if I have $6$ objects , and there must be $2$ sets of $3$ objects, it is physically possible.) Hence, it is actually possible to arrange $3n$ objects with $n$ triplets of object being identical in a row, thus causing the number of ways to be an integer. Henceforth, $\dfrac{(3n)!}{(3!)^n}$ that represents the number of ways to arrange $3n$ objects with $n$ triplets of object being identical, in a row, will thus be an integer.

P.S : If however, the number of objects $<$ number of objects limited by the requirement of the permutation, the scenario will not physically happens. Hence, the expression that evaluates the number of ways might not be an integer. However, since we are not interested in it, we can hence ignore it.

- 5 years, 9 months ago

I believe I have a brilliantly simple solution to your question - I will use induction. Let f(n) = $\frac{(3n)!}{(3!)^{n} }$. Base test: for n=1, f(1) = 1 and f(2) = $\frac{6!}{3! * 3!}$ = $\frac{4 * 5 * 6}{6}$ = 20. Now for the inductive step: $\frac{(3n+3)!}{(3!)^{n} * 3!}$, and by breaking up the fraction we see that f(n+1) is a product of $\frac{(3n)!}{(3!)^{n} }$ and $\frac{(3n+1)(3n+2)(3n+3)}{3!}$. We already know that the former is already an integer by our inductive hypothesis, so we need to prove that the latter is also an integer. This is simple as 3 or more consecutive integers are divisible by 3 and 2 (In fact, n consecutive integers are always divisible by n!). Hence, our proof is complete. I hope that helps :D

- 5 years, 9 months ago