Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
show 4 more comments

2 Answers

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
+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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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