Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Re: Re: Binomial Expansion

by japhy (Canon)
on Mar 29, 2001 at 21:39 UTC ( #68141=note: print w/ replies, xml ) Need Help??


in reply to Re: Binomial Expansion
in thread Binomial Expansion

Ok, for fun, and because I like mathematical proofs (I made it to the USA Mathematic Olympiad twice), here's the proof I use. In pseudo-code, the n-choose-r function looks like:

nCr (n,r) { res = 1; for i in 1 .. r { res *= n; n--; res /= i; } return res; }
The question is, why does res remain an integer? It is not difficult to show that res /= 1 is an integer, but how can we prove that by the time we get to res /= 7, res is a multiple of 7?

The proof is that by the time we have gotten to res /= X, we have multiplied res's original value, 1, by X continuous integer, and in every series of X continuous integers, there will be one number divisible by X:

X = 2, series = (y, y+1); one is div. by 2 X = 3, series = (y, y+1, y+2); one is div. by 3 ... in nCr(17,7), n is of the series (17,16,15,14,13,12,11) i is of the series ( 1, 2, 3, 4, 5, 6, 7) (17/1) (17/1) (16/2) (17/1) (16/2) (15/3) (17/1) (16/4) (15/3) (14/2) (17/1) (16/4) (15/(3*5)) (14/2) (13/1) (17/1) (16/4) (15/(3*5)) (14/2) (13/1) (12/6) (17/1) (16/4) (15/(3*5)) (14/(2*7)) (13/1) (12/6) (11/1)
We're allowed to move the denominators around like I did, because we've already showed the product will already be an integer. The product looks like:
r ----- | | n - (i-1) | | --------- | | i i=1


japhy -- Perl and Regex Hacker


Comment on Re: Re: Binomial Expansion
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://68141]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (4)
As of 2015-07-04 02:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (57 votes), past polls