Prove that $a_1!\cdots a_k! < n!$ whenever $a_1+\cdots+a_k < n$

Question

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?

Answer 1

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

Answer 2

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$.

Answer 3

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$.

Answer 4

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$.

Answer 5

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!$.