Exactly k heads by listing every sequence

List the whole sample space of n coin flips and count the sequences with exactly k heads.

What to build

A program that counts outcomes and favourable outcomes for coin flips.

Requirements

  • Print outcomes N (all sequences of n flips), favourable F (sequences with exactly k heads) and probability P as a reduced fraction (0 or 1 when it is).

Input

One line: n and k.

Output

Three lines.

Constraints

1 ≤ n ≤ 12; 0 ≤ k ≤ n.

Example

Input:

3 2

Output:

outcomes 8
favourable 3
probability 3/8

Why it works

Each of the 2ⁿ sequences is equally likely, so the probability is the share of sequences with k heads; listing them shows where the counts come from.

Examples

Example 1 · Input
3 2
Expected output
outcomes 8
favourable 3
probability 3/8
Example 2 · Input
4 2
Expected output
outcomes 16
favourable 6
probability 3/8

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

itertools.product("HT", repeat=n) gives every sequence of n flips.

Hint 2

str(Fraction(f, total)) prints a reduced fraction, 0 or 1.

Solution

Show one correct solution (try it yourself first)
from fractions import Fraction
from itertools import product

n, k = map(int, input().split())
total = 0
good = 0
for seq in product("HT", repeat=n):
    total += 1
    if seq.count("H") == k:
        good += 1
print("outcomes", total)
print("favourable", good)
print("probability", Fraction(good, total))

Lesson: Outcomes and probability →