A lottery draws k different numbers from 1 to n, and you hold a ticket of k numbers. Work out the chance of matching exactly m of them.
What to build
A program that prints the probability of exactly m matches and the odds against it.
Requirements
- Print
P(match M) = Fwith F a reduced fraction (0when impossible). - Then print
odds 1 in X, where X is the number of tickets divided by the favourable ones, rounded to the nearest whole number, orodds impossiblewhen no draw gives m matches.
Input
One line: n, k and m.
Output
Two lines.
Constraints
1 ≤ k ≤ n ≤ 60; 0 ≤ m ≤ k.
Example
Input:
49 6 6
Output:
P(match 6) = 1/13983816
odds 1 in 13983816
Why it works
Every draw of k numbers is equally likely; the favourable draws pick m of your numbers and the rest from the numbers you did not choose, so the count is a product of two combinations.
Examples
Example 1 · Input
49 6 6
Expected output
P(match 6) = 1/13983816 odds 1 in 13983816
Example 2 · Input
10 3 1
Expected output
P(match 1) = 21/40 odds 1 in 2
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Choose which m of your k numbers match, and which k − m of the other n − k numbers fill the draw.
Hint 2
P = C(k, m) × C(n − k, k − m) ÷ C(n, k); keep it as a Fraction.
Solution
Show one correct solution (try it yourself first)
from fractions import Fraction
from math import comb
n, k, m = map(int, input().split())
total = comb(n, k)
good = comb(k, m) * comb(n - k, k - m)
print(f"P(match {m}) = {Fraction(good, total)}")
print("odds impossible" if good == 0 else f"odds 1 in {round(total / good)}")