1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: A question about factorials, nCr

  1. Jan 26, 2016 #1
    1. The problem statement, all variables and given/known data
    Hi,I found this problem when I was reading a book,I knew the answer but there is one thing that I don't understand.Here is the question:

    Given C(2015,m),find the smaller of m such that C(2015,m) is an even number

    2. Relevant equations

    3. The attempt at a solution
    Here is the answer:(sorry for being quite messy)

    Expand C(2015,m),which gives:

    (2015)(2014)........... (numerator)
    m(m-1)(m-2).....(4)(3)(2)(1)........(2015-m)(2015-m+1)....... (denominator)

    After some arrangement it becomes:

    which is :

    In my book,the answer said the first even number occurs when (2016-m)/m is an even number
    Therefore 2016/m - 1 must be even,then 2016/m must be odd.
    Since 2016 = 2^5 * 63,the smallest number of m is 2^5 = 32

    My question:
    I know the answer is correct.However,let's just expand a few terms up to 2011 (i.e.m=5)

    (5) (4) (3) (2) (1)

    which gives:

    (403)(1007)(671)(503)(2011) = 2.75*(10^14)

    Since m is small,the final product C(2015,m) has a high chance to be an integer as the factors in the denominator is quite small.
    However,how can we ensure this is still the case when m is large(Just say m=32 given in my case),could it be a fraction instead of an even number?There might be terms like (1984/19) which makes the final term neither odd nor even.

    Thanks very much.
  2. jcsd
  3. Jan 26, 2016 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Fact of life: for positive integers N and m (with 0 ≤ m ≤ N), C(N,m) is always an integer.

    For instance: C(N,0) = 1 is an integer; C(N,1) = N is an integer; C(N,2) = N(N-1)/2, and one of the factors in the numerator is even; C(N,3) = N(N-1)(N-2)/(3*2), and one of the factors in the numerator is even and one of them is a multiple of 3.

    It becomes trickier for m larger than 3, but the result is still true.

    Perhaps the easiest way is to do it is to first establish the recursion C(N,m) = C(N-1,m) + C(N-1,m-1), and then use induction on N. That is, given m, let N = m, m+1, m+2, ... .
    Last edited: Jan 26, 2016
  4. Jan 26, 2016 #3


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    There are a couple of ways to see it will always be an integer.
    If you prove Pascal's relationship C(n,r)=C(n-1,r-1)+C(n-1,r) then inductively they are all integers.
    Or consider that if a prime p occurs in some pattern in [1, r] then it occurs in a corresponding pattern in [n-r+1,n]. By that I mean that if p occurs to some power in the lower sequence then there is a corresponding place in the upper sequence where it occurs to at least the same power, and the correspondence is 1-1. That takes a bit of work to make rigorous.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted