My Math Forum  

Go Back   My Math Forum > College Math Forum > Advanced Statistics

Advanced Statistics Advanced Probability and Statistics Math Forum


Thanks Tree2Thanks
  • 1 Post By cjem
  • 1 Post By SDK
Reply
 
LinkBack Thread Tools Display Modes
March 28th, 2018, 04: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.
Jomo is offline  
 
March 28th, 2018, 05:05 PM   #2
Senior Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 284
Thanks: 86

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.
cjem is offline  
March 28th, 2018, 09:21 PM   #3
Newbie
 
Joined: Nov 2013

Posts: 26
Thanks: 8

Quote:
Originally Posted by cjem View Post
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.
All I want to use is that nCr = n!/(r!(n-r)!). Why is that an integer?
Jomo is offline  
March 29th, 2018, 04:10 AM   #4
Senior Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 284
Thanks: 86

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!}{(n-r)!}$.

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!}{(n-r)!}\right)
&= \nu_p (n!) - \nu_p ((n-r)!) \\
&= \sum_{t \geq 1} \left\lfloor \dfrac{n}{p^t} \right\rfloor - \sum_{t \geq 1} \left\lfloor \dfrac{n-r}{p^t} \right\rfloor \\
&\geq \sum_{t \geq 1} \left\lfloor \dfrac{r}{p^t} \right\rfloor \\
&= \nu_p(r!)
\end{align*}$
Thanks from SDK
cjem is offline  
March 29th, 2018, 06:22 AM   #5
SDK
Senior Member
 
Joined: Sep 2016
From: USA

Posts: 520
Thanks: 293

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?
Thanks from cjem
SDK is offline  
March 29th, 2018, 07:15 AM   #6
Senior Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 284
Thanks: 86

Math Focus: Algebraic Number Theory, Arithmetic Geometry
Quote:
Originally Posted by SDK View Post
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.
The inequality simply comes from $\left \lfloor x \right \rfloor + \left \lfloor y \right \rfloor \leq \left \lfloor x + y \right \rfloor$:

For any $t$, we have $\left\lfloor \dfrac{n-r}{p^t} \right\rfloor + \left\lfloor \dfrac{r}{p^t} \right\rfloor \leq \left\lfloor \dfrac{(n-r)+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{n-r}{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 07:22 AM.
cjem is offline  
March 29th, 2018, 08:03 AM   #7
Senior Member
 
Joined: Oct 2009

Posts: 628
Thanks: 190

Or you could use an induction and
$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$
Micrm@ss is offline  
March 29th, 2018, 04:21 PM   #8
Newbie
 
Joined: Nov 2013

Posts: 26
Thanks: 8

Quote:
Originally Posted by SDK View Post
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?
Yes, I followed this. Thank you.
Jomo is offline  
March 29th, 2018, 04:25 PM   #9
Newbie
 
Joined: Nov 2013

Posts: 26
Thanks: 8

Quote:
Originally Posted by cjem View Post
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!}{(n-r)!}$.

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!}{(n-r)!}\right)
&= \nu_p (n!) - \nu_p ((n-r)!) \\
&= \sum_{t \geq 1} \left\lfloor \dfrac{n}{p^t} \right\rfloor - \sum_{t \geq 1} \left\lfloor \dfrac{n-r}{p^t} \right\rfloor \\
&\geq \sum_{t \geq 1} \left\lfloor \dfrac{r}{p^t} \right\rfloor \\
&= \nu_p(r!)
\end{align*}$
I had to think about this a bit (which is good!) and I finally got what you are saying. Thank you.
Jomo is offline  
Reply

  My Math Forum > College Math Forum > Advanced Statistics

Tags
combinatoric, question



Thread Tools
Display Modes


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





Copyright © 2018 My Math Forum. All rights reserved.