# Proving factorial attribute

Given that : $$\sum_{i=1}^{k} a_i = n$$ I am asked to prove that: $$\prod_{j=1}^{k} a_j!$$ divises $n!$

I saw that it works for $k=1$, and for $k=2$ I tried :

$$\frac{n!}{a_1! a_2!} = \frac{(a_1 + a_2)!}{a_1! a_2!}$$

But came to nowhere.

How do I go on? I pretty sure it is by induction

-
It is by induction, but in this case, it requires you to show $k=2$ separately, and the rest follows by induction. – Thomas Andrews Apr 9 '13 at 4:48
Indeed, and that's what I'm trying to do. If I can show it for k=2 then I can do it for k=j, let it be anything, for the induction. But I have to understand how to do k=2 first! – TheNotMe Apr 9 '13 at 4:49
Did you recognize that you can write $\frac{(p+q)!}{p!q!}$ as a binomial coefficient? – J. M. Apr 9 '13 at 4:53
To be honest, no I did not... – TheNotMe Apr 9 '13 at 4:55
Thank you. A binomial coefficient is always a a positive integer in this case. – TheNotMe Apr 9 '13 at 5:00

HINT

Count the number of ways of arranging $n$ balls where $a_1$ balls are of color $1$, $a_2$ balls of color $2$ and in general, $a_j$ balls are of color $j$. (Note that $\displaystyle \sum_{j=1}^k a_j = n$.)

-
Now I get it. It is the binomial coefficient, right? – TheNotMe Apr 9 '13 at 4:59
@Aryabhata I have updated it. Does it read fine now? – user17762 Apr 9 '13 at 6:24
@TheNotMe These are the multinomial coefficients. – user17762 Apr 9 '13 at 6:25
This is more of a question that gives opinion about formality of mathematical proofs. If I say that that number is what this is (arranging the balls), isn't it enough proof that it is an integer? – TheNotMe Apr 9 '13 at 16:48

Hint for induction proof.

If $$\sum_{i=1}^{k} a_j = n$$ then

$$\sum_{i=1}^{k-1} b_i = n$$

where $b_1 = a_1 + a_2, b_2 = a_3, \dots$

Since OP does not seem interested in this hint, for sake of completeness...

$$\dfrac{n!}{\prod_{j=1}^{k} a_j!} = \dfrac{(a_1 + a_2)!}{a_1!a_2!}\cdot\dfrac{n!}{\prod_{j=1}^{k=1} b_j!}$$

which is the product of two integers.

-
+1. Another proof using induction is using the recurrence $$C(n+1;a_1,a_2,a_3,\ldots,a_k) = C(n;a_1-1,a_2,a_3,\ldots,a_k) + C(n;a_1,a_2-1,a_3,\ldots,a_k) + C(n;a_1,a_2,a_3-1,\ldots,a_k) + \cdots + C(n;a_1,a_2,a_3,\ldots,a_k-1)$$ – user17762 Apr 9 '13 at 6:29
@Marvis: I somehow find what I wrote easier :-), and is in fact another way of looking at your counting proof, I believe. – Aryabhata Apr 9 '13 at 6:35