0
$\begingroup$

I believe this is true on intuition, I am just curious about the best means of proving this idea:

Given an integer $n$, then the products of the factorials of a given integer partition on $n$ (excluding $n$ itself) is less than $n!$, i.e.

$4$ has integer partitions (excluding $4$ itself):

  • $3+1$
  • $2+2$
  • $2+1+1$
  • $1+1+1+1$

It is simple to see that the product of the factorials of those integer partitions are less than $4!=24$:

  • $3!\cdot 1!=6$
  • $2!\cdot 2!=4$
  • $2!\cdot 1!\cdot 1!=2$
  • $1!\cdot 1!\cdot 1!\cdot 1!=1$

I assume this requires the generating function?

$\endgroup$

3 Answers 3

2
$\begingroup$

The proof is not too complicated. As an example, here is $2+3+4=9$.

\begin{align} 2! \cdot 3! \cdot 4! &= (1 \cdot 2) \cdot (1 \cdot 2 \cdot 3) \cdot (1 \cdot 2 \cdot 3 \cdot 4)\\ &\le (1 \cdot 2) \cdot (3 \cdot 4 \cdot 5) \cdot (6 \cdot 7 \cdot 8 \cdot 9)\\ &= 9!. \end{align}


Thanks to Ross Millikan for the further clarification. The above example was intended to show how a general proof would look like. If $a_1+\cdots+a_k = n$, then $a_1! \cdots a_k!$ is the product of $n$ integers. It is possible to increase those $n$ integers in such a way to obtain the product $n! = 1 \cdot 2 \cdots n$.

$\endgroup$
4
  • $\begingroup$ I appreciate your answers. I think I should have specified that I meant in the general case... $\endgroup$
    – SumNeuron
    Mar 15, 2017 at 21:21
  • $\begingroup$ The example indicates how to deal with the general case. The product of the factorials of a partition has the same number of factors as the factorial of the partitioned number. The factors are decreased, so the product is less. $\endgroup$ Mar 15, 2017 at 21:23
  • $\begingroup$ Stupid question, how would you show that "If $a_1+\dots+a_k=n$ then $a_1!\dots a_k!$ is the product of $n$ integers" $\endgroup$
    – SumNeuron
    Mar 15, 2017 at 21:33
  • $\begingroup$ @SumNeuron Write out each $a_i!$ as $a_i (a_i-1) (a_i-2) \cdots 2 \cdot 1$. $\endgroup$
    – angryavian
    Mar 16, 2017 at 2:41
1
$\begingroup$

You could generalize this specific style of proof to arbitrary partitions:

To show $n!>a!(n-a)!$ note that

$n!=\prod\limits_{k=1}^n k = \prod\limits_{k=1}^a k \cdot \prod\limits_{k=a+1}^n k > \prod\limits_{k=1}^a k \cdot \prod \limits_{k=a+1}^n (k-a) = a!(n-a)!$

The idea being that for any partition $(a_1,a_2,\dots,a_k)$ of $n$ you have $a_1!a_2!\cdots a_k!$ is written as the product of $n$ terms when expanded, and every term is less than or equal (and at least one term is strictly less than so long as it is partitioned into at least two nonempty parts) than the corresponding terms in the expansion of $n!$.

If you want to be particularly formal, you can induction on the number of parts.

Alternatively, you could use what you know about multinomial coefficients to note that

$\binom{n}{a_1,a_2,\dots,a_k} = \frac{n!}{a_1!a_2!\cdots a_k!}$ is an integer implying $a_1!a_2!\cdots a_k!\leq n!$.

$\endgroup$
3
  • $\begingroup$ I appreciate your answers, the top part is not so clear so if you could maybe elaborate it, that would be appreciated. I was already aware of the multinomial coefficient, but they 1.) do not require one use up all values of $n$ - hence is not necessarily a integer partition and 2.) why I am comfortable with that the multinomial coefficient being > 0 and thus, as you stated, implying that the multinomial coefficient of an integer partition being less than or equal to $n!$, am not satisfied without a more concrete way of showing this.... $\endgroup$
    – SumNeuron
    Mar 15, 2017 at 21:27
  • $\begingroup$ @SumNeuron in fact for a multinomial coefficient $\binom{n}{a_1,a_2,\dots,a_k}$ you do require that $a_1+a_2+\dots+a_k=n$ so yes in fact you do require that $(a_1,a_2,\dots,a_k)$ makes forms a partition (though not necessarily in monotonic order). As for elaborating on the first part, assuming $a>0$ you have $k>k-a$ making the second product to the left of the $>$ sign strictly larger than the second product on the right of the $>$ sign. This is the same observation that avian made, $(1\cdot 2)\cdot (3\cdot 4\cdot 5)>(1\cdot 2)\cdot (1\cdot 2\cdot 3)$ $\endgroup$
    – JMoravitz
    Mar 15, 2017 at 21:31
  • $\begingroup$ As for comparing the multinomial coefficient argument to binomial coefficient arguments, it is the exact same argument except I don't bother saying "you can partition $n$ into $r$ and $n-r$ and you can partition each of those pieces further", I go straight to the final partition $a_1,a_2,\dots,a_k$ $\endgroup$
    – JMoravitz
    Mar 15, 2017 at 21:34
1
$\begingroup$

Since for $n > r$ ;$$\binom{n}{r} > 1$$

$$\frac{n!}{r!(n-r)!} > 1$$

$$\implies n ! ~> ~r~! \times (n-r)!$$

Here $n$ and $(n-r)$ are partitions of $n$.

You can divide $r$ and $(n-r)$ further into partitions, that'll ultimately result into partitions of $n$.

$$\implies n! > a_1!~a_2!~a_3!~ \dots a_k!~~~~~~~~ \text{; where} ~\sum_{i=1}^{k}a_i=n $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .