
Advanced Statistics Advanced Probability and Statistics Math Forum 
 LinkBack  Thread Tools  Display Modes 
March 28th, 2018, 03:26 PM  #1 
Newbie Joined: Nov 2013 Posts: 26 Thanks: 8  Combinatoric question
I was wondering how one could prove that nCr is an integer. Yes, I do know that you can say that it is by definition but I was looking for a proof not involving a counting argument.

March 28th, 2018, 04:05 PM  #2 
Senior Member Joined: Aug 2017 From: United Kingdom Posts: 211 Thanks: 64 Math Focus: Algebraic Number Theory, Arithmetic Geometry 
It really depends on what definition you're using for nCr. If the one you're using is such that it's an integer by definition, then it's an integer by definition! No counting argument necessary. Otherwise, it would not be okay to say it's an integer by definition. 
March 28th, 2018, 08:21 PM  #3 
Newbie Joined: Nov 2013 Posts: 26 Thanks: 8  All I want to use is that nCr = n!/(r!(nr)!). Why is that an integer?

March 29th, 2018, 03:10 AM  #4 
Senior Member Joined: Aug 2017 From: United Kingdom Posts: 211 Thanks: 64 Math Focus: Algebraic Number Theory, Arithmetic Geometry 
Okay, sure. I'm in a bit of a rush right now, so I'll write up a very brief argument. I'll be happy to clarify things later if needed. What we want to show is that $r!$ divides $\dfrac{n!}{(nr)!}$. Let $p$ be a prime, and denote by $\nu_p$ the $p$adic valuation. It's not hard to show that $\nu_p(x!) = \sum_{t \geq 1} \left\lfloor \dfrac{x}{p^t} \right\rfloor$ for any integer $x$. Therefore $\begin{align*} \nu_p \left(\dfrac{n!}{(nr)!}\right) &= \nu_p (n!)  \nu_p ((nr)!) \\ &= \sum_{t \geq 1} \left\lfloor \dfrac{n}{p^t} \right\rfloor  \sum_{t \geq 1} \left\lfloor \dfrac{nr}{p^t} \right\rfloor \\ &\geq \sum_{t \geq 1} \left\lfloor \dfrac{r}{p^t} \right\rfloor \\ &= \nu_p(r!) \end{align*}$ 
March 29th, 2018, 05:22 AM  #5 
Senior Member Joined: Sep 2016 From: USA Posts: 417 Thanks: 231 Math Focus: Dynamical systems, analytic function theory, numerics 
A slightly more elementary observation (which I think is the reason for the inequality on the 2nd to last line in cjem's solution thought I'm not sure) is the following fact. Fix $m \in \mathbb{N}$ and let $P$ be the product of $m$many consecutive positive integers Then $m! \leq P$. This is fairly easy to prove. Here is a sketch which may help. $P$ has the form \[P = \prod_{j = 1}^m (k + j) \] for some $k \in \mathbb{N}$. Obviously we have equality if $k = 0$. Now, fix any prime $q \in \mathbb{N}$ and argue the following: 1. $P$ has at least as many multiples of $q$ as $m!$ does. To see this, count the multiples of $q$ when you reduce any $m$ consecutive integers modulo $q$. 2. The result in 1 also holds if we replace $q$ with powers of $q$. 3. For each prime, $q$, dividing $m!$, each occurrence is either a multiple of $q$ or a multiple of $q^s$ with $s >1$. The results in (1),(2) says $P$ has at least as many occurrences of each of these as $m!$ so $P$ has at least as many occurrences of $q$ as $m!$ does. This result holds for any $m \in \mathbb{N}$. Do you see why this now immediately implies that $\binom{n}{k}$ is an integer? 
March 29th, 2018, 06:15 AM  #6  
Senior Member Joined: Aug 2017 From: United Kingdom Posts: 211 Thanks: 64 Math Focus: Algebraic Number Theory, Arithmetic Geometry  Quote:
For any $t$, we have $\left\lfloor \dfrac{nr}{p^t} \right\rfloor + \left\lfloor \dfrac{r}{p^t} \right\rfloor \leq \left\lfloor \dfrac{(nr)+r}{p^t} \right\rfloor = \left\lfloor \dfrac{n}{p^t} \right\rfloor$. Hence $\left\lfloor \dfrac{n}{p^t} \right\rfloor  \left\lfloor \dfrac{nr}{p^t} \right\rfloor \geq \left\lfloor \dfrac{r}{p^t} \right\rfloor$. Now just sum over $t$ to get the inequality in my post. Last edited by cjem; March 29th, 2018 at 06:22 AM.  
March 29th, 2018, 07:03 AM  #7 
Senior Member Joined: Oct 2009 Posts: 436 Thanks: 147 
Or you could use an induction and $$\binom{n}{k} = \binom{n1}{k1} + \binom{n1}{k}$$ 
March 29th, 2018, 03:21 PM  #8  
Newbie Joined: Nov 2013 Posts: 26 Thanks: 8  Quote:
 
March 29th, 2018, 03:25 PM  #9  
Newbie Joined: Nov 2013 Posts: 26 Thanks: 8  Quote:
 

Tags 
combinatoric, question 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Combinatoric!!!  eChung00  Applied Math  2  October 5th, 2012 01:04 AM 
combinatoric!!  eChung00  Applied Math  1  September 17th, 2012 04:25 PM 
Combinatoric/Probability Question  wulfgarpro  Probability and Statistics  3  June 2nd, 2010 12:59 PM 
Combinatoric question  wulfgarpro  Algebra  2  June 1st, 2010 12:49 AM 
Discrete  a basic combinatoric question  Ezekiel  Applied Math  2  September 11th, 2008 07:36 PM 