Counting Foundations

Applied Combinatorics (CC BY-SA) · appliedcombinatorics.org

Two rules generate almost everything. Sum rule: if choices are mutually exclusive, add. Product rule: if choices are made in sequence, multiply. Permutations count ordered selections; combinations count unordered ones. Everything downstream is bookkeeping on top of these.

Permutations: order matters

An ordered selection of k items from n is a permutation. The first slot has n choices, the next n−1, and so on: P(n,k) = n! / (n−k)!. When k = n you get n! orderings of the whole set.

Combinations: order doesn't

If the order of the chosen items is irrelevant, divide out the k! ways each unordered set could have been ordered: C(n,k) = n! / (k!(n−k)!). This is the binomial coefficient, and it runs the rest of the subject.

Scheme

; The three primitives of counting
(define (factorial n)
  (if (<= n 1) 1 (* n (factorial (- n 1)))))

; P(n,k): ordered selections of k from n
(define (perm n k)
  (/ (factorial n) (factorial (- n k))))

; C(n,k): unordered selections of k from n
(define (choose n k)
  (/ (factorial n) (* (factorial k) (factorial (- n k)))))

(display "5! = ") (display (factorial 5)) (newline)
(display "P(5,2) = ") (display (perm 5 2)) (newline)   ; 20
(display "C(5,2) = ") (display (choose 5 2)) (newline)  ; 10

; a 4-digit PIN: order matters, repeats allowed -> product rule
(display "PINs = ") (display (expt 10 4)) (newline)     ; 10000

Neighbors

🔢 Discrete Math Ch.1 — the introductory take on counting
🎲 Probability — counting outcomes is the foundation of discrete probability

by june.kim Binomial Coefficients · 2 of 10 →