Counting Principles

Probability Theory

Count Without Listing Every Outcome

Counting principles give you formulas for the number of ways events can occur — without actually listing them all. They are the foundation of probability calculations.

Multiplication principle — Multiply choices across independent stages
Permutations — Order matters; arrange r items from n distinct items
Combinations — Order does not matter; choose r items from n
Binomial coefficient — The number of ways to choose r successes from n trials

Counting is the bridge between "how many ways" and "what is the probability."

What is the Fundamental Counting Principle?

Definition

If there are ways to do task 1, ways to do task 2, and so on, the total number of ways to do all tasks is their product.

# Example: 3 shirts, 4 pants, 2 shoes
shirts = 3
pants = 4
shoes = 2
total_outfits = shirts * pants * shoes
print(f"Total outfits = {shirts} × {pants} × {shoes} = {total_outfits}")

Factorials

import math
from itertools import permutations, combinations

# Factorials
for n in range(1, 8):
    print(f"{n}! = {math.factorial(n)}")

Permutations (Order Matters)

# Permutations: arranging 3 books from 5
n, r = 5, 3
perm = math.perm(n, r)
print(f"P({n}, {r}) = {n}!/{n-r}! = {perm}")

# List all permutations
books = ['A', 'B', 'C', 'D', 'E']
for p in permutations(books, 3):
    print(f"  {p}")

Combinations (Order Doesn't Matter)

# Combinations: choosing 3 books from 5
n, r = 5, 3
comb = math.comb(n, r)
print(f"C({n}, {r}) = {n}!/({r}!×{n-r}!) = {comb}")

# List all combinations
for c in combinations(books, 3):
    print(f"  {c}")

Permutations with Repeated Elements

# Arranging letters in "MISSISSIPPI"
from collections import Counter

word = 'MISSISSIPPI'
counts = Counter(word)
denominator = math.prod(math.factorial(v) for v in counts.values())
result = math.factorial(len(word)) // denominator

print(f"'{word}' has {len(word)} letters")
print(f"Letter counts: {dict(counts)}")
print(f"Distinct arrangements = {len(word)}!/({' × '.join(str(v) for v in counts.values())}) = {result}")

Counting Principles in Machine Learning

ML Application	Counting Usage	Why
Combinatorial optimization	Hyperparameter search space	Grid/random search
Permutation tests	Statistical significance	Non-parametric testing
Neural architecture search	Architecture combinations	NAS search space

import numpy as np
from math import factorial

# Hyperparameter search space
n_lr = 5  # learning rates to try
n_layers = 4  # layer depths to try
n_units = 3  # unit sizes to try

total_combinations = n_lr * n_layers * n_units
print(f"Grid search space: {n_lr} × {n_layers} × {n_units} = {total_combinations} combinations")

# Permutation test for significance
np.random.seed(42)
group_a = np.random.normal(50, 10, 30)
group_b = np.random.normal(55, 10, 30)
observed_diff = group_b.mean() - group_a.mean()

# Random permutations
n_perms = 10000
combined = np.concatenate([group_a, group_b])
count = 0
for _ in range(n_perms):
    np.random.shuffle(combined)
    perm_diff = combined[:30].mean() - combined[30:].mean()
    if perm_diff >= observed_diff:
        count += 1

p_value = count / n_perms
print(f"\nObserved difference: {observed_diff:.2f}")
print(f"Permutation p-value: {p_value:.4f}")
print(f"Significant: {'Yes' if p_value < 0.05 else 'No'}")

Counting Principles — Permutations and Combinations