#!/usr/bin/env python
#--------------------------------------------------------------------
#	megawin.py
#
#	This program will compute the probability that a Califormia 
#	MegaMillions lottery ticket matches all six winning numbers
#	by using a recursive calculation for binomial coefficients.
#
#		execute using:  $ python megawin.py
#
#	programmer: ALLAN CRUSE
#	written on: 27 JAN 2011
#--------------------------------------------------------------------

def binomial( n, k ):
	if ( n < 0 ) or ( k < 0 ) or ( n < k ):
		return 0
	else:
		if ( n == 0 ) or ( k == 0 ) or ( k == n ):
			return	1
		else:
			return	binomial( n-1, k-1 ) + binomial( n-1, k )

print
print "Computing the number of different California",
print "MegaMillions lottery tickets"
print
m = binomial( 56, 5 )
print "Number of ways to choose 5 things from 56 things is %d " % m
n = binomial( 46, 1 )
print "Number of ways to choose 1 thing from 46 things is %d " % n
s = m * n
print "So the number of MegaMillions tickets is the product",
print "(i.e., %d) " % s
print
f = 1.0/(1.0 * s)
print "The probability your ticket matches all six winning numbers",
print "is %1.10f " % f
print