How Does the Prime Factorization of Binomial Coefficients Work?

[zzzcreepyzzz]

Combinatorial math question. Please help!

Prove that the exponent on a prime p in the prime factorization of
<br /> \binom{2n}{n}\right)\left<br />
is the number of powers p^k of p such that [2n/p^k] is odd. Use this to determine which primes divide
<br /> \binom{18}{9}\right)\left<br />
and which divide
<br /> \binom{20}{10}\right)\left<br />






My problem is, I don't even understand this concept in the first place. Can someone please help me to solve this problem as well as recommend me a good book that could help me clarify topics on combinatorial math?
Thanks in advance!

 

[HallsofIvy]

I presume that you know, at least, the definition:
\left(\begin{array}{c}m \\ n\end{array}\right)= \frac{m!}{n!(m-n)!}

Replacing m with 2n,
\left(\begin{array}{c}2n \\ n\end{array}\right)= \frac{(2n)!}{n!n!}
and, since (2n)!= (2n)(2n-1)(2n-2)... (n)(n-1)... (3)(2)(1), one of those n! in the denominator will cancel the lower part of that:
\frac{(2n)!}{n!n!}= \frac{(2n)(2n-1)(2n-3)...(n+1)(n)}{n(n-1)...(3)(2)(1)}
Now half of the factors in the numerator will be even: 2 times some number less than or equal to n, so will cancel a factor in the denominator.

As an example, take n= 4.
\left(\begin{array}{c}8 \\ 4\end{array}\right)= \frac{8!}{4!4!}
= \frac{(8)(7)(6)(5)(4)(3)(2)(1)}{[(4)(3)(2)(1)][(4)(3)(2)(1)]}= \frac{(8)(7)(6)(5)}{(4)(3)(2)(1)}
= \frac{ (2\cdot 4)(7)(2\cdot 3)(5)}{(4)(3)(2)(1)}= (2)(7)(2)(5)
The positive primes there are 5 and 7 each occurring once because the integer part of 8 divided by either is 1. Of course, 3 is also prime. But 3 divides into 8 2 and 2/3 times. The integer part of that is 2."3" occurred in the binomial coefficient once, in the part 4(3)(2)(1) that got canceled and the second time multiplied by 2, so canceled again. It is only the odd multiples that don't get canceled which is why we only count the number of times that [2n/p^k] is odd.