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;
}
[download]

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)
[download]

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
[download]

japhy -- Perl and Regex Hacker

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.