zzzcreepyzzz

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

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?

Related Calculus and Beyond Homework Help News on Phys.org

HallsofIvy

Homework Helper

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 occuring 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" occured 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.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving