note
japhy
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:
<code>
nCr (n,r) {
res = 1;
for i in 1 .. r {
res *= n;
n--;
res /= i;
}
return res;
}
</code>
The question is, why does <tt>res</tt> remain an integer? It is not difficult to show that <tt>res /= 1</tt> is an integer, but how can we prove that by the time we get to <tt>res /= 7</tt>, <tt>res</tt> is a multiple of 7?
<p>
The proof is that by the time we have gotten to <tt>res /= <i>X</i></tt>, we have multiplied <tt>res</tt>'s original value, 1, by <i>X</i> continuous integer, and in every series of <i>X</i> continuous integers, there will be one number divisible by <i>X</i>:
<code>
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)
</code>
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:
<code>
r
-----
| | n - (i-1)
| | ---------
| | i
i=1
</code>
<br><br>
<tt><font color="#0000ff">japhy</font></tt> --
<a href="/index.pl?node=japhy&lastnode_id=1072">Perl and Regex Hacker</a>
68056
68077