• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Combinatorial math question. Please help

Combinatorial math question. Please help!!!

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






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

Science Advisor
Homework Helper
41,682
864
Re: Combinatorial math question. Please help!!!

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

Replacing m with 2n,
[tex]\left(\begin{array}{c}2n \\ n\end{array}\right)= \frac{(2n)!}{n!n!}[/tex]
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:
[tex]\frac{(2n)!}{n!n!}= \frac{(2n)(2n-1)(2n-3)...(n+1)(n)}{n(n-1)...(3)(2)(1)}[/tex]
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.
[tex]\left(\begin{array}{c}8 \\ 4\end{array}\right)= \frac{8!}{4!4!}[/tex]
[tex]= \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)}[/tex]
[tex]= \frac{ (2\cdot 4)(7)(2\cdot 3)(5)}{(4)(3)(2)(1)}= (2)(7)(2)(5)[/tex]
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.
 

Related Threads for: Combinatorial math question. Please help

Replies
1
Views
790
Replies
1
Views
1K
  • Posted
Replies
2
Views
1K
  • Posted
Replies
6
Views
896
  • Posted
Replies
0
Views
3K

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
Top