Permutations & Combinations

Combinatorics is the branch of mathematics dealing with combinations of objects belonging to a finite set in accordance with certain constraints, such as those of graph theory. In simpler terms: it’s the art of counting.

Before we can calculate probabilities, we must know how to count total outcomes. This chapter builds the foundation for everything that follows.

1. The Fundamental Counting Principle

If you have m ways to do one thing and n ways to do another, then there are m × n ways to do both.

[!NOTE] This is also known as the Multiplication Rule. It extends to any number of events.

Intuition: The Tree Diagram

Why do we multiply? Imagine a decision tree.

First Branch: You make your first choice (e.g., choose a Shirt). This splits your reality into m paths.
Second Branch: From each of those m paths, you make your second choice (e.g., choose Pants). This splits each path into n new paths.

The total number of leaf nodes (outcomes) is the sum of n branches repeated m times, which is exactly definition of multiplication: m × n.

Example: The Outfit Problem

Shirts: 3 (Red, Blue, Green)
Pants: 2 (Jeans, Chinos)
Total Outfits: 3 × 2 = 6 unique combinations.

2. Factorials: The Engine of Counting

To understand permutations and combinations, we first need to understand the factorial. The factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n.

Formula: n! = n × (n-1) × (n-2) × … × 1
Special Case: 0! = 1

Hardware Reality: The 64-bit Wall

Factorials grow explosively. In computer science, this causes Integer Overflow.

32-bit signed integer: Max value is ~2 billion (2³¹-1). It can only hold up to 12! (479,001,600). 13! overflows.
64-bit signed integer: Max value is ~9 quintillion (2⁶³-1). It can only hold up to 20! (~2.4 × 10¹⁸). 21! overflows.

[!WARNING] If you try to calculate 21! using a standard long in Java or int64 in Go, you will get a garbage negative number due to wrap-around overflow. This is why we must use arbitrary-precision arithmetic (BigInteger) for combinatorial math.

3. Permutations: Order Matters

A Permutation is an arrangement of items in a specific order. Think of a Password or a Podium finish in a race. {Gold, Silver, Bronze} is different from {Bronze, Silver, Gold}.

Formula

The number of permutations of n distinct items taken k at a time is:

P(n, k) = n! / (n-k)!

n: Total number of items
k: Number of items to arrange

Example: Code Lock

A lock has digits 0-9 (10 digits). You need a 3-digit code, and digits cannot be repeated.

n = 10
k = 3
P(10, 3) = 10! / (10-3)! = 10! / 7! = 10 × 9 × 8 = 720 possibilities.

4. Combinations: Order Doesn’t Matter

A Combination is a selection of items where order does not matter. Think of a Committee or a Card hand. {Ace, King, Queen} is the same hand as {Queen, King, Ace}.

Formula

The number of combinations of n distinct items taken k at a time is:

C(n, k) = n! / (k!(n-k)!)

Intuition: Start with the Permutation formula P(n, k). This gives you all ordered arrangements.
Since order doesn’t matter, {A, B, C} is the same as {C, B, A}. There are k! ways to arrange k items.
We divide P(n, k) by k! to remove these duplicates.

Also denoted as _nC_k or “n choose k”.

Example: Lottery

Choose 3 winning numbers from 10.

n = 10
k = 3
C(10, 3) = 10! / (3! × 7!) = (10 × 9 × 8) / (3 × 2 × 1) = 720 / 6 = 120 possibilities.

Permutation vs Combination Explorer

Total Items (n): 5

Items to Choose (k): 2

* k cannot exceed n

Permutations (Order Matters)

P(n, k) = n! / (n-k)!

Combinations (Order Doesn't Matter)

C(n, k) = n! / (k!(n-k)!)

Visualizing Outcome Space (Limited to first 20)

Permutations

Combinations

5. Implementation Examples

Java

In Java, we typically use BigInteger for factorials to avoid overflow, as n! grows extremely fast (13! exceeds 32-bit int, 21! exceeds 64-bit long).

import java.math.BigInteger;

public class Combinatorics {

    // Calculate Factorial: n!
    public static BigInteger factorial(int n) {
        BigInteger result = BigInteger.ONE;
        for (int i = 2; i <= n; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result;
    }

    // Calculate Permutations: P(n, k) = n! / (n-k)!
    public static BigInteger permutations(int n, int k) {
        if (k > n) return BigInteger.ZERO;
        // Optimization: P(n, k) is n * (n-1) * ... * (n-k+1)
        BigInteger result = BigInteger.ONE;
        for (int i = 0; i < k; i++) {
            result = result.multiply(BigInteger.valueOf(n - i));
        }
        return result;
    }

    // Calculate Combinations: C(n, k) = P(n, k) / k!
    public static BigInteger combinations(int n, int k) {
        if (k > n) return BigInteger.ZERO;
        BigInteger numerator = permutations(n, k);
        BigInteger denominator = factorial(k);
        return numerator.divide(denominator);
    }

    public static void main(String[] args) {
        int n = 10;
        int k = 3;
        System.out.println("P(" + n + ", " + k + ") = " + permutations(n, k)); // 720
        System.out.println("C(" + n + ", " + k + ") = " + combinations(n, k)); // 120
    }
}

Go

Go also supports big integers via the math/big package.

package main

import (
	"fmt"
	"math/big"
)

// Factorial calculates n!
func Factorial(n int64) *big.Int {
	res := big.NewInt(1)
	if n <= 1 {
		return res
	}
	return res.MulRange(1, n)
}

// Permutations P(n, k)
func Permutations(n, k int64) *big.Int {
	if k > n {
		return big.NewInt(0)
	}
	// P(n, k) = n! / (n-k)!
	// Equivalent to MulRange(n-k+1, n)
	res := big.NewInt(1)
	return res.MulRange(n-k+1, n)
}

// Combinations C(n, k)
func Combinations(n, k int64) *big.Int {
	if k > n {
		return big.NewInt(0)
	}
	// C(n, k) = n! / (k! * (n-k)!)
	// Optimization: C(n, k) = C(n, n-k). Use smaller k.
	if k > n/2 {
		k = n - k
	}

	numerator := Permutations(n, k)
	denominator := Factorial(k)

	return new(big.Int).Div(numerator, denominator)
}

func main() {
	var n, k int64 = 10, 3
	fmt.Printf("P(%d, %d) = %s\n", n, k, Permutations(n, k)) // 720
	fmt.Printf("C(%d, %d) = %s\n", n, k, Combinations(n, k)) // 120
}

Python (for Machine Learning)

In Machine Learning, we don’t calculate these by hand. We use Python’s standard libraries or scientific stack.

import math
import itertools

n = 10
k = 3

# Permutations: Order matters
# Formula: n! / (n-k)!
perms = math.perm(n, k)
print(f"Permutations P({n}, {k}): {perms}")
# Output: 720

# Combinations: Order doesn't matter
# Formula: n! / (k! * (n-k)!)
combs = math.comb(n, k)
print(f"Combinations C({n}, {k}): {combs}")
# Output: 120

# Generating actual items
items = ['A', 'B', 'C']
# Order matters: ('A', 'B') != ('B', 'A')
print(list(itertools.permutations(items, 2)))

6. Real-World ML Application: Feature Selection

Why does this matter in Machine Learning?

Imagine you have a dataset with 20 features (columns), but you want to train a model using only 3 features to avoid overfitting (a technique called “Best Subset Selection”).

How many different models do you need to train and evaluate?

Since the order of features doesn’t matter for the model (Feature A + Feature B is the same model as Feature B + Feature A), this is a Combination problem.

C(20, 3) = 20! / (3! × 17!) = (20 × 19 × 18) / (3 × 2 × 1) = 1,140 models

The Complexity Explosion

What if you have 100 features and want to select 10?

C(100, 10) ≈ 1.73 × 10¹³ models

That is 17 trillion models. This explains why we cannot brute-force feature selection and instead use heuristic methods like:

Forward Selection (Greedy algorithm)
Lasso Regularization (L1 penalty)
Random Forests (Feature importance)

[!TIP] Understanding the scale of combinations helps you recognize when a problem is computationally intractable and requires an approximation algorithm.