1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorial math question. Please help

  1. Feb 22, 2009 #1
    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!
     
  2. jcsd
  3. Feb 22, 2009 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Combinatorial math question. Please help
Loading...