Counting is not about listing things one by one. It is about finding the size of a set without enumeration, using structure: addition when choices are disjoint, multiplication when choices are independent, and correction terms when they overlap.
Additive and multiplicative principles
If you can do task A in m ways or task B in n ways, and the two sets of outcomes are disjoint, you have m + n total options. If you must do A then B, and the choices are independent, you have m * n options. These two rules generate the rest of combinatorics.
Scheme
; Additive principle: disjoint union; A restaurant offers 4 soups OR 5 salads as a starter.; Total starters = 4 + 5 = 9
(define soups 4)
(define salads 5)
(display "Starters (add): ")
(display (+ soups salads)) (newline)
; Multiplicative principle: cartesian product; You pick a soup AND a main (3 options).; Total meals = 4 * 3 = 12
(define mains 3)
(display "Soup+main combos (multiply): ")
(display (* soups mains))
C(n,k) = n! / (k!(n-k)!) counts the number of k-element subsets of an n-element set. It answers "how many ways can I choose k items from n when order doesn't matter?" The same numbers appear as coefficients in (x+y)^n, which is why they are called binomial coefficients.
Scheme
; C(n,k) = n! / (k! * (n-k)!); Compute using the multiplicative formula to avoid big factorials.
(define (choose n k)
(if (or (= k 0) (= k n))
1
(/ (* (choose (- n 1) (- k 1)) n) k)))
(display "C(5,3) = ") (display (choose 53)) (newline)
(display "C(10,4) = ") (display (choose 104)) (newline)
; Pascal's identity: C(n,k) = C(n-1,k-1) + C(n-1,k)
(display "C(4,2) + C(4,3) = ")
(display (+ (choose 42) (choose 43))) (newline)
(display "C(5,3) = ")
(display (choose 53))
A permutation is an ordered arrangement: P(n,k) = n!/(n-k)!. A combination ignores order: C(n,k) = P(n,k)/k!. The ratio k! captures exactly the redundant orderings within each chosen subset.
How many ways can you distribute n identical objects into k distinct bins? Place n stars in a row and insert k-1 bars to create k groups. The answer is C(n+k-1, k-1). This reframes a distribution problem as a subset-selection problem.
Scheme
; Stars and bars: distribute n identical items into k bins.; Answer: C(n + k - 1, k - 1)
(define (fact n)
(if (<= n 1) 1 (* n (fact (- n 1)))))
(define (choose n k)
(/ (fact n) (* (fact k) (fact (- n k)))))
(define (stars-and-bars n k)
(choose (+ n k -1) (- k 1)))
; Distribute 7 cookies among 3 kids
(display "7 cookies, 3 kids: ")
(display (stars-and-bars 73)) (newline) ; C(9,2) = 36; Distribute 5 balls into 4 boxes
(display "5 balls, 4 boxes: ")
(display (stars-and-bars 54)) ; C(8,3) = 56
When sets overlap, naive addition overcounts. PIE corrects: |A union B| = |A| + |B| - |A intersect B|. For three sets, add back the triple intersection. The pattern alternates signs. This is the counting world's version of the Mobius function.
Scheme
; PIE for two sets:; |A union B| = |A| + |B| - |A intersect B|; How many integers from 1 to 100 are divisible by 2 or 3?
(define div2 (quotient 1002)) ; 50
(define div3 (quotient 1003)) ; 33
(define div6 (quotient 1006)) ; 16 (divisible by both)
(define union (- (+ div2 div3) div6))
(display "Div by 2: ") (display div2) (newline)
(display "Div by 3: ") (display div3) (newline)
(display "Div by 6: ") (display div6) (newline)
(display "Div by 2 or 3: ") (display union) (newline) ; 67; PIE for three sets:; |A union B union C| = |A|+|B|+|C| - |AB| - |AC| - |BC| + |ABC|
(define div5 (quotient 1005)) ; 20
(define div10 (quotient 10010)) ; 10
(define div15 (quotient 10015)) ; 6
(define div30 (quotient 10030)) ; 3
(define union3
(+ (- (+ div2 div3 div5)
(+ div6 div10 div15))
div30))
(display "Div by 2, 3, or 5: ") (display union3) ; 74
Python
# PIE for two sets
div2 = 100 // 2# 50
div3 = 100 // 3# 33
div6 = 100 // 6# 16print(f"Div by 2 or 3: {div2 + div3 - div6}") # 67# PIE for three sets
div5 = 100 // 5# 20
div10 = 100 // 10
div15 = 100 // 15
div30 = 100 // 30
result = div2 + div3 + div5 - div6 - div10 - div15 + div30
print(f"Div by 2, 3, or 5: {result}") # 74
Notation reference
Math
Scheme
Python
Meaning
C(n,k)
(choose n k)
comb(n, k)
Binomial coefficient
P(n,k)
(perm n k)
perm(n, k)
k-permutation of n
n!
(fact n)
factorial(n)
Factorial
|A union B|
(- (+ a b) ab)
a + b - ab
Inclusion-exclusion (2 sets)
C(n+k-1, k-1)
(stars-and-bars n k)
comb(n+k-1, k-1)
Stars and bars
Neighbors
Other chapter pages
Grinstead Ch.3 โ combinatorics reappears in computing probabilities
Levin's textbook builds counting from careful set-theoretic arguments. The Scheme implementations here use exact integer arithmetic, so no overflow or rounding issues for moderate inputs. The multiplicative formula for C(n,k) avoids computing full factorials. Python's math.comb (3.8+) does the same internally.
Binomial coefficient