3
$\begingroup$

In my book, under Legendre’s Function, the following two examples were given;

When $m,n \in N$ , prove that;

  1. $\ $ $m! \cdot (n!)^m$ divides $(mn)!$

  2. $\ $ $m! \cdot n! \cdot (m+n)! $ divides $(2m)! \cdot (2n)!$

Well, for the first one, I know it is just the number of ways to put $mn$ balls into $m$ identical baskets, each with $n$ balls.

But, as this is a NT book, I tried solving this with Legendre’s Function and it just did not work,

I got we needed to prove:

$f(mn) \ge f(m) + m \cdot f(n)$ where $f(k) = [\frac{k}{p}]$ where [.] is the floor function.

Now, I could not figure out what to do, I tried inducting on $n$ but after using some inequalities like $[xy] \ge [x][y]$ and $[x+y] \ge [x]+[y]$ , the inequality just became false.

As I couldn't even solve the first one, I could not solve the second one either, not even 'combinatorically'.

So, I am looking for a proof of both the problems using Legendre’s Function (and perhaps a combinatorial proof of $2$ well?)

Thanks!

$\endgroup$
6
  • $\begingroup$ Wait is it $[k/p]$ or is it $[k/p]+[k/p^2]+\dotsb$? $\endgroup$ Apr 11 at 11:33
  • $\begingroup$ the latter, but i thought proving using [k/p] would be equivalent / easier $\endgroup$ Apr 11 at 11:46
  • $\begingroup$ $m=n=p=2$ is a counterexample to what you wanted to show. Better work with the full screen version I think. $\endgroup$ Apr 11 at 12:10
  • $\begingroup$ @ZachTeitler , i tried the problem again now but i'm not sure how to deal with infinite sum inequalities with floor function; can you pls give me a hint? $\endgroup$ Apr 11 at 12:53
  • 1
    $\begingroup$ In this answer it is shown that $$\frac{(mn)!}{(m!)^nn!}=\prod_{k=1}^n\binom{mk-1}{m-1}$$ $\endgroup$
    – robjohn
    Apr 11 at 22:46
5
$\begingroup$

The second question follows from the following inequality: let $x,y$ be real numbers, then $[x]+[y]+[x+y] \leq [2x]+[2y]$.

Here’s a very easy proof: the inequality is unchanged when integers are added to $x,y$, so we can assume $0 \leq x,y <1$, and we want to show $[x+y] \leq [2x]+[2y]$. But $0 \leq x+y,2x,2y< 2$, so that the only case where the inequality isn’t trivial is when $[2x]+[2y]=0$, ie $[2x]=[2y]=0$, ie $x,y < 0.5$. But then $x+y <1$ and the inequality holds.

For 1), we need to show that for any prime $p$, any integers $m,n$, $\sum_{k \geq 1}{m[n/p^k]+[m/p^k]} \leq \sum_{k \geq 1}{[mn/p^k]}$. Let $l \geq 2$ be minimal such that $p^l >n$ (if $p > n$ then it’s trivial). Then for any $k \geq 1$, $[m/p^k] \leq [mn/p^{k+l-1}]$. Thus $\sum_{k \geq 1}{[m/p^k]} \leq \sum_{k \geq l}{[mn/p^k]}$. Moreover, $\sum_{k \geq 1}{m[n/p^k]} \leq \sum_{k=1}^{l-1}{m[n/p^k]} \leq \sum_{1 \leq k < l}{[mn/p^k]}$ and this ends the proof.

$\endgroup$
1
  • $\begingroup$ Woah thanks so much, i guess i should have tried the second problem also as the inequality you used was the problem right before this one. Thank you once again! $\endgroup$ Apr 11 at 13:16
3
$\begingroup$

I think the combinatorial argument for 2. could go like this: let's define $g$ as the ratio $$ g(m,n) = \frac{(2m)!(2n)!}{m!n!(m+n)!} $$ We can observe that $$ g(m,n-1)=\frac{(2m)!(2n-2)!}{m!(n-1)!(m+n-1)!} = \frac{n(m+n)\color{blue}{(m+1)}}{2n(2n-1)\color{blue}{(m+1)}}g(m,n) $$ and $$ g(m+1,n-1)=\frac{(2m+2)!(2n-2)!}{(m+1)!(n-1)!(m+n)!} = \frac{n(2m+1)(2m+2)}{2n(2n-1)(m+1)}g(m,n) $$ (the blue-marked $(m+1)$ has obviously been added to match the second expression). Now, expanding the products on the respective RHS, we see that the numerators are $$ N_1=nm^2+n^2+mn+mn^2 \\ N_2=4nm^2+6nm+2n $$ and the denominator is $$ D=(4n^2-2n)(m+1) = 4n^2m+4n^2-2nm-2n $$ It's not too hard to see that $$ \begin{aligned} 4N_1-N_2 &= 4(nm^2+n^2+mn+mn^2) - (4nm^2+6nm+2n) \\ &= 4n^2m+4n^2-2nm-2n \\ &= D \end{aligned}$$ Therefore it follows that $$ \implies g(m,n)=4g(m,n-1)-g(m+1,n-1) $$ Using this formula iteratively, we can now see that $$ g(m,n) = \sum\nolimits_j \sum\nolimits_k a_{j,k} g(k,0) $$ All $a_{j,k}$ are integers and $$ g(k,0)=\frac{(2k)!}{k!k!} = \frac{(2k)!}{k!(2k-k)!} = \binom{2k}{k} $$ is a binomial coefficient.

$\endgroup$
2
  • $\begingroup$ wow, this is really cool! Thanks! $\endgroup$ Apr 12 at 5:37
  • $\begingroup$ @Aditya_math not as elegant as robjohn's in my opinion. I had no idea where he was going until the very last step. Beautiful. $\endgroup$ Apr 12 at 13:07
2
$\begingroup$

Question $\bf{1}$

In this answer, it is shown that $$ \frac{(mn)!}{(m!)^nn!}=\prod_{k=1}^n\binom{mk-1}{m-1}\tag1 $$


Question $\bf{2}$

Using the equation $x=\lfloor x\rfloor+\{x\}$, we get the equation $$ \lfloor 2x\rfloor+\lfloor 2y\rfloor-\lfloor x\rfloor-\lfloor y\rfloor-\lfloor x+y\rfloor=\{x\}+\{y\}+\{x+y\}-\{2x\}-\{2y\}\tag2 $$ There are two possibilities: if $\{x\}+\{y\}\lt1$ $$ \{x+y\}=\{x\}+\{y\}\tag{3a} $$ or if $\{x\}+\{y\}\ge1$ $$ \{x+y\}=\{x\}+\{y\}-1\tag{3b} $$ If $\{x\}\lt\frac12$ and $\{y\}\lt\frac12$, then $\text{(3a)}$ implies $$ \{x\}+\{y\}+\overbrace{\{x+y\}}^{\{x\}+\{y\}}-\overbrace{\{2x\}}^{2\{x\}}-\overbrace{\{2y\}}^{2\{y\}}=0\tag{4a} $$ If $\{x\}\ge\frac12$ and $\{y\}\ge\frac12$, then $\text{(3b)}$ implies $$ \{x\}+\{y\}+\overbrace{\{x+y\}}^{\{x\}+\{y\}-1}-\overbrace{\{2x\}}^{2\{x\}-1}-\overbrace{\{2y\}}^{2\{y\}-1}=1\tag{4b} $$ Otherwise, assume $\{x\}\ge\frac12$ and $\{y\}\lt\frac12$, then if $\{x\}+\{y\}\,{\color{#C00}{\lt}\atop\color{#090}{\ge}}\,1$ $$ \{x\}+\{y\}+\overbrace{\{x+y\}}^{\{x\}+\{y\}-{\color{#C00}{0}\atop\color{#090}{1}}}-\overbrace{\{2x\}}^{2\{x\}-1}-\overbrace{\{2y\}}^{2\{y\}}={\color{#C00}{1}\atop\color{#090}{0}}\tag{4c} $$ Thus, $(2)$ and $(4)$ ensure that $$ \lfloor 2x\rfloor+\lfloor 2y\rfloor-\lfloor x\rfloor-\lfloor y\rfloor-\lfloor x+y\rfloor\ge0\tag5 $$ Therefore, for any prime $p$, $$ \overbrace{\sum_{k=1}^\infty\left(\left\lfloor\frac{2n}{p^k}\right\rfloor+\left\lfloor\frac{2m}{p^k}\right\rfloor\right)}^\text{factors of $p$ in $(2n)!(2m)!$}\ge\overbrace{\sum_{k=1}^\infty\left(\left\lfloor\frac{n}{p^k}\right\rfloor+\left\lfloor\frac{m}{p^k}\right\rfloor+\left\lfloor\frac{n+m}{p^k}\right\rfloor\right)}^\text{factors of $p$ in $n!m!(n+m)!$}\tag6 $$ That is, $$ n!\,m!\,(n+m)!\mid(2n)!\,(2m)!\tag7 $$

$\endgroup$
2
  • $\begingroup$ this is really beautiful... thanks! I'll have to read this again to completely wrap my head around this $\endgroup$ Apr 12 at 20:06
  • $\begingroup$ I'm glad you liked this answer. However, the point of $(2)$-$(4)$ was to show $(5)$ using fractional parts; whereas Mindlack used integer parts to show the same thing with less work. Both answers aim at showing $(6)$, which by Legendre, shows $(7)$. $\endgroup$
    – robjohn
    Apr 12 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.