Probability on finite sets reduces to counting. Permutations count ordered arrangements, combinations count unordered selections, and the binomial coefficient C(n, k) = n! / (k!(n-k)!) ties them together. Pascal's triangle is the lookup table.
Permutations โ order matters
A permutation of n objects is an arrangement in a specific order. There are n! = n × (n-1) × ... × 1 permutations. If you only arrange k objects out of n, there are n!/(n-k)! ways (the "falling factorial" P(n,k)).
Scheme
; Factorial and permutations
(define (factorial n)
(if (<= n 1) 1 (* n (factorial (- n 1)))))
; P(n, k) = n! / (n-k)! โ ordered arrangements of k from n
(define (permutations n k)
(/ (factorial n) (factorial (- n k))))
(display "5! = ") (display (factorial 5)) (newline)
; How many ways to arrange 3 books from a shelf of 5?
(display "P(5,3) = ") (display (permutations 53)) (newline)
; How many ways to seat 4 people in 4 chairs?
(display "P(4,4) = ") (display (permutations 44))
A combination selects k items from n without caring about order. C(n, k) = n! / (k!(n-k)!). This is the binomial coefficient, often written "n choose k." It counts the number of k-element subsets of an n-element set.
Scheme
; C(n, k) = n! / (k! * (n-k)!)
(define (factorial n)
(if (<= n 1) 1 (* n (factorial (- n 1)))))
(define (choose n k)
(/ (factorial n)
(* (factorial k) (factorial (- n k)))))
; How many 5-card hands from a 52-card deck?
(display "C(52,5) = ") (display (choose 525)) (newline)
; How many ways to choose 3 toppings from 8?
(display "C(8,3) = ") (display (choose 83)) (newline)
; Key identity: C(n,k) = C(n, n-k)
(display "C(10,3) = ") (display (choose 103)) (newline)
(display "C(10,7) = ") (display (choose 107))
Each entry in Pascal's triangle is C(n, k). The entry equals the sum of the two entries above it: C(n, k) = C(n-1, k-1) + C(n-1, k). The n-th row gives the coefficients of (a + b)^n.
Scheme
; Pascal's triangle: each entry = sum of two above
(define (factorial n)
(if (<= n 1) 1 (* n (factorial (- n 1)))))
(define (choose n k)
(/ (factorial n)
(* (factorial k) (factorial (- n k)))))
; Build row n of Pascal's triangle
(define (pascal-row n)
(let loop ((k 0) (row '()))
(if (> k n) (reverse row)
(loop (+ k 1) (cons (choose n k) row)))))
; Print first 6 rows
(let loop ((n 0))
(when (< n 6)
(display "n=") (display n) (display ": ")
(display (pascal-row n)) (newline)
(loop (+ n 1))))
The binomial theorem
(a + b)^n = ∑ C(n, k) a^k b^(n-k) for k from 0 to n. This connects algebra to counting. Setting a = b = 1 gives 2^n = ∑ C(n, k), the total number of subsets of an n-element set.
Scheme
; Binomial theorem: (a + b)^n = sum of C(n,k) * a^k * b^(n-k)
(define (factorial n)
(if (<= n 1) 1 (* n (factorial (- n 1)))))
(define (choose n k)
(/ (factorial n)
(* (factorial k) (factorial (- n k)))))
(define (binomial-expand a b n)
(let loop ((k 0) (total 0))
(if (> k n) total
(loop (+ k 1)
(+ total (* (choose n k)
(expt a k)
(expt b (- n k))))))))
; (1+1)^4 = 2^4 = 16
(display "(1+1)^4 = ") (display (binomial-expand 114)) (newline)
; (2+3)^3 = 5^3 = 125
(display "(2+3)^3 = ") (display (binomial-expand 233)) (newline)
; Sum of all C(n,k) for n=10 = 2^10 = 1024
(display "sum C(10,k) = ") (display (binomial-expand 1110))
Counting for probability
With uniform distributions, P(E) = |E|/|Ω|. Combinatorics gives you |E| and |Ω|. The probability of exactly k heads in n fair coin flips is C(n, k) / 2^n.
Scheme
; P(exactly k heads in n fair flips) = C(n,k) / 2^n
(define (factorial n)
(if (<= n 1) 1 (* n (factorial (- n 1)))))
(define (choose n k)
(/ (factorial n)
(* (factorial k) (factorial (- n k)))))
(define (coin-prob n k)
(/ (choose n k) (expt 2 n)))
; 10 flips
(display "P(5 heads in 10 flips) = ")
(display (exact->inexact (coin-prob 105))) (newline)
(display "P(3 heads in 10 flips) = ")
(display (exact->inexact (coin-prob 103))) (newline)
; Poker: P(flush) = C(4,1)*C(13,5) / C(52,5)
(define p-flush (/ (* (choose 41) (choose 135)) (choose 525)))
(display "P(flush) = ")
(display (exact->inexact p-flush))
Python
# Counting for probabilityfrommathimport comb
def coin_prob(n, k):
return comb(n, k) / 2**n
print(f"P(5 heads in 10) = {coin_prob(10, 5):.4f}")
print(f"P(3 heads in 10) = {coin_prob(10, 3):.4f}")
# Poker flush
p_flush = comb(4,1) * comb(13,5) / comb(52,5)
print(f"P(flush) = {p_flush:.6f}")
Permutation