1
$\begingroup$

Prove that for positive integers $a_1,\dots,a_k$ (where $k\geq 1)$ are such that $a_1+\cdots+a_k < n$ , then $a_1!\cdots a_k! < n!$.

So far, i've tried adding the condition that suppose they were also in increasing order. I've thought about using induction to prove it, but it seems like this is not the right approach to go about this. Without induction, I am struggling to somehow use the fact that:

$$a_1+\cdots+a_k < n \implies (a_1+\cdots+a_k)! < n! $$ and relate $\displaystyle \left(\sum a_i\right)!$ to $\displaystyle \prod a_i!$. How does one proceed?

$\endgroup$
  • 1
    $\begingroup$ By the way, since you are only dealing with commutative operations ($+$ and $\cdot$), "in increasing order" is hardly a condition to add but rather an assumption you can make without problems. $\endgroup$ – SK19 Feb 15 '18 at 8:56
2
$\begingroup$

Hint: $2!\times 3!=(1\times 2)\times (1\times 2\times 3)\lt (1\times 2)\times (3\times 4\times 5)$

$\endgroup$
  • $\begingroup$ Although I have answered the question in my own style and your hint has helped my to come up with a second answer, I somehow doubt your intend was to hint at double induction. May I ask what proof sketch you had in mind? $\endgroup$ – SK19 Feb 15 '18 at 9:29
  • 1
    $\begingroup$ @SK19 I was just thinking that you could define $b_m$ as $r$ when $m=\sum_0^ua_t+r\le \sum_0^{u+1}a_t$ and then $b_m=r\le m$ and the product of the $b_m$ is less than or equal to the product of $m$ which is $\le n!$ (sorry, that's a sketch and there I've been having problems getting all the indices right and making sure the empty sum is a possibility - but I hope you get the idea. $\endgroup$ – Mark Bennet Feb 15 '18 at 10:04
2
$\begingroup$

I can do better. I can prove that $$ m = \frac{n!}{a_1!a_2!\cdots a_k!} $$ is a natural number greater than $1$.

Consider the following situation: You have $a_1$ identical red balls, $a_2$ identical blue balls, ..., $a_k$ identical green balls, and finally $n-(a_1+a_2+\cdots+a_k)$ numbered white balls. Then $m$ is exactly the number of different ways you can order these balls in a line, which means that $m$ is an integer. Since there is at least one red ball and one white ball, there are at least two ways to do this, so $m\geq2$.

Note that unless $k = 1$ and $a_1 = n$, then we only need to require that $a_1+\cdots + a_k\leq n$ (as opposed to ${}<n$) for $m$ to be greater than $1$.

$\endgroup$
  • $\begingroup$ In fact $m\ge\frac{n!}{(n-k+1)!}$ which is very much larger than 2. :) $\endgroup$ – user Feb 15 '18 at 8:55
  • $\begingroup$ @user355705 Not if $k=1, a_1=1,n=2$. $\endgroup$ – Arthur Feb 15 '18 at 9:23
  • $\begingroup$ @user355705 Note that one of the premises was $n>a_1+\cdots+a_k$. So we can't have $a_1 = n = k = 1$ or $n = k = 2, a_1 = a_2 = 1$. In other words, we must have at least one white ball. And yes, it's pretty clear that one can very often set up the balls in line in much more than $2$ ways. I don't need to use $\frac{n!}{(n-k+1)!}$ to point that out, although it does help with demonstrating the scale of it. $\endgroup$ – Arthur Feb 15 '18 at 9:39
  • $\begingroup$ If $k=1$, then $m=1$ and your inequality is invalidated (mine - not). :) My point was however that the inequality $m\ge\frac{n!}{(n-k+1)!}$ is stronger than $m\ge2$ reducing to it for $n=2,a_1=a_2=1$. $\endgroup$ – user Feb 15 '18 at 9:41
  • $\begingroup$ @user355705 And my point was that no, we can't have the cases where you say my inequality is invalidated. It's not allowed from the premises of the problem (you seem to think that we have $a_1+\cdots + a_k = n$, but we don't). And also, the problem was to show that $m>1$, and therefore proving that $m\geq 2$ is enough. In addition, $m = 2$ is possible, so for a constant bound, that is the best one can do. If you want to introduce variables to the bound, then of course we can do better. $\endgroup$ – Arthur Feb 15 '18 at 9:43
1
$\begingroup$

Induction over $k$ is also possible, although it appears to be more complicated than my other answer, as it uses induction within induction.

$k=1$ is clear. For the induction step we will need $a!b!<(a+b)!$ (I). This it itself provable by induction, the induction step goes $$(a+1)!b!<(a+1)(a+b)!<(a+b+1)(a+b)!=(a+b+1)!$$

Set $S_k=a_1+\ldots+a_k$ and $P_k=a_1!\cdot\ldots\cdot a_k!$.

Now assume the conjecture holds for a certain $k$. Then we have especially $P_k<(S_k+1)!$ since $S_k < S_k+1$. Now the smallest $n_0$ for which $S_{k+1}<n_0$ holds is of course $S_{k+1}+1$. Now with (I) we get $$P_{k+1} = P_k \cdot a_{k+1}! < (S_k+1)!\cdot a_{k+1}! < (S_k+1+a_{k+1})!=(S_{k+1}+1)!$$

So, within our induction step (over $k$) we can now perform an additional induction (over $n$), where we, just like in my first answer, get the induction step (over $n$) for free (since $n<n+1$ and $n!<(n+1)!$ hold) and just need to prove the induction start (which we just did above). Hence our conjuncture of this specific $k+1$ holds for all $n$ with $S_{k+1}<n$, and that concludes our induction proof (over $k$), henceforth we have shown the conjuncture to be true for all $k$.

$\endgroup$
1
$\begingroup$

Well, why not use induction? Let's induce over $n$. In this case, the induction step is clear (since $n<n+1$ and $n!<(n+1)!$), so we concentrate on the induction start for any given $k$ and $a_1,\ldots,a_k$. Let's denote $A:=a_1+\ldots+a_k$. The smallest $n_0$ satisfying $A < n_0$ is $A+1$. So we are left to proof $$\prod_{i=1}^k(a_i!) < (A+1)!$$ Now we take logarithms on both sides and are left to show $$\log\prod_{i=1}^k(a_i!) < \log((A+1)!)$$(this is equivalent to the other statement because $\log x$ and $e^x$ are monotone functions and we are dealing with natural numbers ($\geq 1$) everywhere.) After using logarithm laws, the Gauss sum and multiplying both sides with $2$, we get $$A+\sum_{i=1}^k a_i^2 < A^2 + 3A + 2$$ Now, when we remember that $$A^2 = \sum_{i,j=1}^k a_i a_j$$ we can see that the inequality holds, so our first inequality holds, too, and therefore our induction start is proven.

Of course, for writing it down the standard would be to go like $$2\log\prod_{i=1}^k(a_i!) = \ldots = A+\sum_{i=1}^k a_i^2 < A + \sum_{i,j=1}^k a_ia_j < A^2 + 3A +2 = \ldots = 2\log((A+1)!)$$ and then one would conclude with the monotony of $e^x$.

$\endgroup$
1
$\begingroup$

I would have argued with an intuitiv combinatorical argument about permuting balls and permuting balls in certain groups. But here is how to do it rigirously.


Let $X$ be an $n$-element set and $X=A_1\cup\cdots\cup A_k$ a partition into disjoint sets. Define $a_i:=|A_i|$, then $a_1+\cdots+a_k=n$. Given permutations $\sigma_i:A_i\to A_i,i=1,...,k$, we can define a permutation $$\sigma:X\to X, \quad\sigma(x)=\sigma_i(x) \;\text{if $x\in A_i$}.$$

This mapping $(\sigma_1,...,\sigma_k)\mapsto \sigma$ is an injection of the set

$$\underbrace{\mathrm{Sym}(A_1)\times\cdots\times \mathrm{Sym}(A_k)}_{a_1!\,\cdots\, a_k! \text{ elements}}\quad\text{into}\quad\underbrace{\mathrm{Sym}(X)}_{n! \text{ elements}}.$$

Hence $a_1!\cdots a_k!\le n!$.

$\endgroup$

Your Answer

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