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.
Multiplication Principle
Here,
- =Number of choices for each task
# 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
Factorial
Here,
- =n factorial — product of all positive integers up to n
- =By definition
import math
from itertools import permutations, combinations
# Factorials
for n in range(1, 8):
print(f"{n}! = {math.factorial(n)}")
Permutations (Order Matters)
DfPermutation
A permutation is an arrangement of objects in a specific order. The number of permutations of n objects taken r at a time is n!/(n-r)!.
Permutations
Here,
- =Total number of objects
- =Number of objects to arrange
- =Number of ordered arrangements
# 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)
DfCombination
A combination is a selection of objects where order does not matter. The number of combinations of n objects taken r at a time is n!/(r!(n-r)!).
Combinations (Binomial Coefficient)
Here,
- =Read as 'n choose r'
- =Total number of objects
- =Number of objects to select
# 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
Permutations with Repetition
Here,
- =Counts of each repeated element
# 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'}")
Key Takeaways
Summary: Counting Principles
- Multiplication principle: total ways = product of choices for each independent task
- Factorial (n!) = product of all integers from 1 to n — counts arrangements
- Permutations P(n,r) = n!/(n-r)! — ordered arrangements of r from n
- Combinations C(n,r) = n!/(r!(n-r)!) — unordered selections of r from n
- Order matters -> permutations; order doesn't -> combinations
- Python tools: math.factorial(), math.perm(), math.comb(), itertools.permutations(), itertools.combinations()