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.

Hello the question is as stated above and is given to us in the context of group theory, specifically under the heading of isomorphism and products. I would write down what I have tried so far but I have made very little progress in trying to solve this over the last few hours!

share|improve this question
1  
If it were me I would write "Yes it does, it's a binomial coefficient", context be damned. –  Hammerite Jan 31 '13 at 11:31

4 Answers 4

up vote 17 down vote accepted

Hint: Find an injective group homomorphism $S_a \times S_b \hookrightarrow S_{a+b}$.

share|improve this answer
1  
Presumably, you mean a group injection, not a set injection. –  Thomas Andrews Jan 30 '13 at 19:54
    
Yes, I edited my answer accordingly. –  marlu Jan 30 '13 at 19:56
3  
ahhhh so if i define an injective homomorphism then $S_a \times S_b$ will be isomorphic to the image which is then a subgroup of $S_{a+b}$ and so it is a divisor. Thanks –  Ben Jan 30 '13 at 20:04

The number of ways to choose $a$ objects out of $a+b$ objects if order matters in the selection is $(a+b)\times(a+b-1)\times\cdots\times((a+b)-(a-1))=\frac{(a+b)!}{b!}$, since there are $a+b$ ways to choose the first object, $a+b-1$ ways to choose the second object from the remaining ones, and so on.

However, $a!$ permutations actually correspond to a single combination (where order is immaterial), since $a$ objects can be arranged in $a!$ ways. This means that $\frac{(a+b)!}{b!}=ka!$ for some integer $k$, so that $(a+b)!=ka!b!$.

share|improve this answer
1  
Isn't this kind of circular reasoning? How do we know that formula is the number of ways to choose $a$ objects out of $a+b$ objects? Can you prove this without proving the formula yields an integer along the way? –  MartianInvader Jan 30 '13 at 21:33
2  
This still feels like it leaves out the important details... like someone asking "Why does the order of a subgroup divide the order of the group" and someone answering "Because of Lagrange's theorem." –  MartianInvader Jan 30 '13 at 21:45
    
I think your edit made it less clear. –  Jim Jan 31 '13 at 0:41
    
I really like this solution...It's with posts like this that I wish I could up-vote twice! ;-) –  amWhy Feb 4 '13 at 1:07

A proof based on the binomial recurrence: $\frac{(a+b)!}{a!b!} ( =\binom{a+b}{a}) =: f(a,b)$ fulfills the following recurrence:

$f(a,b) = f(a-1,b) + f(a,b-1), \quad a>0,b>0$

with starting values

$f(a,0) = f(0,a) = 1, \quad a \ge 0$

so by induction for all non-negative integer values $a,b$ the function $f(a,b)=\frac{(a+b)!}{a!b!}$ is an integer value.

share|improve this answer
    
It's good that you show the definition of the combinatorial parenthetically. It's really incidental to the question posed. –  Jim Jan 31 '13 at 0:42

A proof based on prime factorization:

Let $e(N,p)$, $p$ a prime, be the exponent of $p$ in the prime factorization of $N$. Then we have to show:

For all primes $p$: $e(a!,p)+e(b!,p) \le e((a+b)!,p)$.

We have

$e(n!,p) = [\frac{n}{p}] + [\frac{n}{p^2}] + \cdots, \quad$ where $[r]$ is the largest integer $\le r$.

We also have

$[\frac{a}{k}] + [\frac{b}{k}] \le [\frac{a+b}{k}] \quad$ for any positive integers $a,b,k$.

From these two propositions the claim follows directly.

share|improve this answer
    
If we define $\sigma_p(n)$ to be the sum of the base-$p$ digits of $n$, then $$e(n!,p)=\frac{n-\sigma_p(n)}{p-1}$$ –  robjohn Jan 30 '13 at 21:04
    
@robjohn and coproc: Would you mind giving proofs for both of your expressions for $e(n!,p)$? –  Hansen Jan 3 at 17:24
    
@Hansen: my formula is proven in this answer. –  robjohn Jan 3 at 20:11

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.