PROBABILITY & STATISTICS / 1. COUNTING & COMBINATORICS

Counting — Permutations & Combinations

Counting outcomes precisely — the foundation of probability

EXPLANATION

Before you can compute probabilities, you need to count outcomes correctly.

Fundamental Counting Principle:
If event A can happen in m ways and event B in n ways, together they can happen in m × n ways.

Permutations — ORDER MATTERS:
P(n, r) = n! / (n-r)!
"How many ways to arrange r items from n?"
Example: 3-digit PIN from digits 0-9 with no repeat = P(10,3) = 720

Combinations — ORDER DOES NOT MATTER:
C(n, r) = n! / (r! × (n-r)!)  also written as ⁿCᵣ or C(n,r)
"How many ways to choose r items from n?"
Example: Choose 3 students from 10 for a team = C(10,3) = 120

Key insight: C(n,r) = P(n,r) / r! — combinations are permutations divided by the number of ways to arrange the chosen items (which we don't care about).

With repetition:
• Permutations with repetition: nʳ
• Combinations with repetition: C(n+r-1, r)

DIAGRAM

n=4 items: {A, B, C, D}  choose r=2

  Permutations (order matters): AB ≠ BA
  AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC
  P(4,2) = 4!/(4-2)! = 12

  Combinations (order doesn't matter): AB = BA
  AB, AC, AD, BC, BD, CD
  C(4,2) = 4!/(2! × 2!) = 6

  Pascal's Triangle (combinations):
  C(0,0) = 1
  C(1,0) C(1,1) = 1 1
  C(2,0) C(2,1) C(2,2) = 1 2 1
  C(3,0) C(3,1) C(3,2) C(3,3) = 1 3 3 1
  Each entry = sum of two above it

CODE

PYTHON
1import math
2from itertools import permutations, combinations
3import numpy as np
4
5# ── Permutations: P(n, r) = n! / (n-r)! ─────────────────────────
6def perm(n, r):
7    return math.factorial(n) // math.factorial(n - r)
8
9print(f"P(10,3) = {perm(10, 3)}")     # 720 — 3-digit PINs no repeat
10print(f"P(5,5)  = {perm(5, 5)}")      # 120 — arrange all 5 items
11
12# ── Combinations: C(n, r) = n! / (r! * (n-r)!) ───────────────────
13def comb(n, r):
14    return math.comb(n, r)   # built-in since Python 3.8
15
16print(f"C(10,3) = {comb(10, 3)}")     # 120 — choose 3 from 10
17print(f"C(52,5) = {comb(52, 5)}")     # 2,598,960 — poker hands
18
19# ── Enumerate actual permutations/combinations ────────────────────
20items = ['A', 'B', 'C', 'D']
21
22print("\nPermutations of 2 from {A,B,C,D}:")
23for p in permutations(items, 2):
24    print(p, end="  ")
25
26print("\n\nCombinations of 2 from {A,B,C,D}:")
27for c in combinations(items, 2):
28    print(c, end="  ")
29
30# ── Real examples ─────────────────────────────────────────────────
31# Probability of a specific poker hand
32total_hands  = comb(52, 5)
33royal_flush  = 4            # one per suit
34prob_royal   = royal_flush / total_hands
35print(f"\n\nP(royal flush) = {prob_royal:.8f}")   # 0.00000154
36
37# Ways to form a committee of 3 from 5 men and 4 women
38# with exactly 2 men and 1 woman
39ways = comb(5, 2) * comb(4, 1)
40total = comb(9, 3)
41print(f"P(2 men, 1 woman) = {ways}/{total} = {ways/total:.4f}")
42
43# ── Multinomial coefficient (arrangements with repeats) ───────────
44# How many ways to arrange "MISSISSIPPI"?
45from collections import Counter
46word = "MISSISSIPPI"
47freq = Counter(word)
48n    = len(word)
49denom = math.prod(math.factorial(v) for v in freq.values())
50arrangements = math.factorial(n) // denom
51print(f"\nArrangements of '{word}': {arrangements:,}")   # 34,650
← PREVOverviewNEXT →2. Probability Axioms & Events