Counting Principles

All 6 orderings collapse to 1

Symmetry property: C(n, r) = C(n, n−r)

Choosing 3 from 9 is equivalent to choosing which 6 to leave out — same result:

Pascal's Triangle and Pascal's Identity

Pascal's identity: C(n, r) = C(n−1, r−1) + C(n−1, r)

Intuition: consider whether item n is included. If yes, choose r−1 from the remaining n−1. If no, choose r from n−1. The two cases are mutually exclusive and exhaustive.

Pascal's triangle puts this into visual form — each entry is the sum of the two entries above it, and the row-n entries are C(n, 0), C(n, 1), ..., C(n, n):

Row 4 reads: C(4,0)=1, C(4,1)=4, C(4,2)=6, C(4,3)=4, C(4,4)=1.

These are the binomial coefficients — they appear directly in the Binomial distribution formula.

Binomial Coefficient → Binomial Distribution

The payoff for learning combinations: C(n, k) counts the number of sequences with exactly k successes in n trials. Multiply by the probability of any one such sequence:

Concrete example: What is the probability that exactly 4 out of 6 CV folds score above 0.85, assuming each fold has a 50% chance independently? (p=0.5 used for illustration — in practice you'd estimate p from data.)

There are 15 ways to pick which 4 folds score above 0.85. Each such pattern has probability 0.5⁶ = 0.015625. Total: 15 × 0.015625 = 0.234.

Without C(6, 4) there is no way to count the 15 favorable sequences — the probability formula has no numerator.

Permutations with Repetition

When items can be reused — n choices at each of r positions:

Formula: n^r

• Hex color codes (16 characters 0-9 and A-F, 6 positions): 16⁶ = 16,777,216
• Hidden state sequences of length 5 from a vocabulary of 10 tokens: 10⁵ = 100,000
• Password with 26 lowercase letters, length 8: 26⁸ ≈ 208 billion

Combinations with Repetition (Stars and Bars)

Choosing r items from n categories where repetition is allowed and order does not matter:

Formula: C(n + r − 1, r)

ML example: Allocating 10 attention heads across 3 transformer layers (a layer can have 0 heads):

There are 66 distinct ways to distribute 10 identical heads across 3 layers. The "stars and bars" intuition: picture 10 stars (heads) separated by 2 bars (dividers between 3 layers) — count the arrangements of 12 symbols with 2 bars.

Combinatorial Explosion

The practical lesson for ML:

• Feature selection: 30 features → 2³⁰ ≈ 1 billion possible subsets
• Hyperparameter search: 5 parameters × 10 values each → 10⁵ = 100,000 configurations
• Neural architecture search: even a modest 20-layer network with 5 choices per layer → 5²⁰ ≈ 95 trillion

This is why greedy forward selection, genetic algorithms, random search, and Bayesian optimization all exist — they navigate combinatorially large spaces without checking every point.

from math import comb, perm

n = 30
print(f"Subsets of {n} features (2^n):      {2**n:>20,}")
print(f"Permutations P({n}, 10):              {perm(n, 10):>20,}")
print(f"Combinations C({n}, 10):              {comb(n, 10):>20,}")
print()
# Grid search: 5 hyperparameters, 10 values each
configs = 10**5
print(f"Grid search (5 params × 10 values): {configs:>20,}")

# Binomial coefficient example
print(f"\nC(6, 4) = {comb(6, 4)}")
print(f"P(exactly 4 of 6 folds above 0.85, p=0.5) = {comb(6,4) * 0.5**6:.4f}")

# Combinations with repetition (stars and bars)
print(f"\nAllocate 10 heads across 3 layers: C(12, 10) = {comb(12, 10)}")

Related Concepts

Counting principles are the discrete foundation of probability theory. Once you can count favorable and total outcomes, you can compute exact probabilities — leading directly to the Binomial distribution (probability of k successes in n trials), the Hypergeometric distribution (sampling without replacement), and the Multinomial distribution (k categories in n trials). Permutations appear in ranking problems and ordered hypothesis testing. Combinations appear in cross-validation fold selection, feature subset enumeration, and network architecture counting. Stirling's approximation connects combinatorics to information theory — log-likelihoods involve sums of log-factorials.

When This Breaks Down

Counting formulas assume all items are distinguishable and selections are uniform (each outcome equally likely). If items are identical, overcounting occurs — the formula changes. If items have different probabilities of being selected, weighted counting is needed. For very large n, exact factorial computation overflows standard floating-point (10^309 for float64); use math.lgamma (log-gamma) or scipy.special.comb(n, k, exact=True) instead. Finally: counting gives you the denominator of a probability — it does not tell you whether the equally-likely assumption is valid.

Test Your Understanding

1. A grid search has 4 hyperparameters: learning rate (5 options), batch size (3 options), dropout (4 options), optimizer (2 options). How many total configurations exist? If you randomly evaluate 1 configuration, what is the probability it has the optimal learning rate?

2. You have 8 candidate models and need to choose 3 to present to stakeholders. How many possible presentation sets exist? If you also need to decide which of the 3 to present first, second, and third, how many ordered presentations exist?

3. Derive the symmetry property C(n, r) = C(n, n−r) algebraically from the formula. Then show numerically for C(7, 2) and C(7, 5).

4. Using Pascal's identity C(n, r) = C(n−1, r−1) + C(n−1, r), compute C(5, 2) without using the factorial formula. Show each step.

5. A model predicts correctly on each of 10 independent test cases with probability p = 0.8. Compute P(X = 8) — the probability of exactly 8 correct predictions. What counting principle makes this calculation possible?