gistfile1.py

#!/usr/bin/env python
#
# This Python 2.7 script solves the following probability problem:

#    If 20 distinct positive integers are chosen from the range 1 - 80
#    (without replacement) what is the probability that their sum is 810?

#              Source: Kim Zafra, http://lnkd.in/bmg4AR5

# Remarks:
#    Let f(m, n, p) be the number of ways to represent m as the sum of
#    n distinct integers in the range 1 to p.
#    Then f(m, n, p) = f(m, n, p-1) + f(m-p, n-1, p-1) provided that
#    m >= p >= 1 and n >= 1.

#    Note that f(0, 0, 0) = 1, since the empty set has sum 0, but in
#    all other cases f(m, n, 0) = 0.

#    We store the values of f(m, n, p) in an 811 x 21 array that is
#    updated 80 times. It initially contains the values of f(m, n, 0). 

from fractions import Fraction

F = [[0]*21 for _ in range(811)]
F[0][0] = 1

for p in range(1, 81):
    for m in range(810, p-1, -1):
        for n in range(20, 0, -1):
            F[m][n] += F[m-p][n-1]

N = F[810][20] 
D = 2*sum(F[m][20] for m in range(810)) + N 
print "The number of combinations is ", N
print "The probability is %s, which is about %f" % (1.0*N/D, Fraction(N,D))