Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
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

In reply to Re: Re: Binomial Expansion by japhy
in thread Binomial Expansion by crazyinsomniac

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others exploiting the Monastery: (6)
    As of 2014-08-02 00:28 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      Who would be the most fun to work for?















      Results (53 votes), past polls