Combinatorics — Counting Without Listing

Real-world analogy

What is it?

Combinatorics is the branch of mathematics that deals with counting, arranging, and choosing things. Instead of listing out every possibility (which could take years for large numbers), it gives us formulas and principles to calculate the count directly. In competitive programming, combinatorics problems are everywhere — from counting paths to choosing teams.

Real-world relevance

Combinatorics is used in everything from lottery probability (how many ticket combinations exist?) to computer science (how many different passwords can be made?), biology (how many ways can DNA bases combine?), and even card games (how many different poker hands are possible?). Every time you wonder 'how many ways can this happen?', you're thinking about combinatorics.

Key points

• The Multiplication Principle — If you have A choices for one thing and B choices for another, the total number of combined choices is A × B. Picking a shirt (4 options) and pants (3 options)? That's 4 × 3 = 12 outfits. This extends to any number of independent choices — just keep multiplying! It's the foundation of all counting.
• The Addition Principle — If you can do something in A ways OR in B ways (but not both at the same time), the total is A + B. For example, if you can take the bus (3 routes) or the train (2 routes) to school, you have 3 + 2 = 5 ways to get there. Use addition when choices are alternatives, and multiplication when choices are combined.
• Factorial — The Building Block — Factorial of n (written n!) means multiplying all numbers from 1 to n. So 5! = 5 × 4 × 3 × 2 × 1 = 120. It tells you how many ways you can arrange n things in a line. Factorials grow SUPER fast — 10! is already 3,628,800 and 20! is astronomically huge. By convention, 0! = 1.
• Permutations (nPr) — Order Matters — A permutation counts how many ways you can pick r items from n items when the ORDER matters. The formula is nPr = n! / (n-r)!. For example, how many ways can 3 runners finish 1st, 2nd, 3rd out of 8? That's 8P3 = 8! / 5! = 8 × 7 × 6 = 336 ways. Gold-silver-bronze is different from bronze-silver-gold!
• Combinations (nCr) — Order Doesn't Matter — A combination counts how many ways you can pick r items from n items when order does NOT matter. The formula is nCr = n! / (r! × (n-r)!). Choosing 3 friends from a group of 8 to form a team? That's 8C3 = 56. Picking Alice-Bob-Carol is the same team as Carol-Alice-Bob, so we divide out the rearrangements.
• Pascal's Triangle — Pascal's Triangle is a magical number triangle where each entry is the sum of the two entries above it. Row n of Pascal's Triangle contains all the values of nCr for r = 0 to n. It starts with row 0: just the number 1. Row 1 is 1, 1. Row 2 is 1, 2, 1. This gives us a fast way to build up combination values without computing huge factorials.
• Combinations with Modular Arithmetic — In CP, answers often get astronomically large, so problems ask for the result modulo some number (usually 1,000,000,007). To compute nCr mod p, we precompute factorials and their modular inverses using Fermat's Little Theorem. This lets us calculate huge combinations without overflow. It's a very common technique in contests!
• Common Counting Patterns in CP — Many CP problems boil down to counting: how many paths in a grid? (Use combinations!) How many subsets of a set? (2^n — each element is either in or out.) How many ways to arrange items with restrictions? (Permutations with constraints.) Recognizing these patterns is the key skill. Once you spot the counting structure, the formula usually follows.

Code example

#include <bits/stdc++.h>
using namespace std;

// Compute factorial up to n
vector<long long> fact;
void precompute(int n) {
    fact.resize(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i;
    }
}

// Compute nCr using precomputed factorials
long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] / (fact[r] * fact[n - r]);
}

int main() {
    precompute(20); // factorials up to 20!

    // Print Pascal's Triangle (first 8 rows)
    cout << "Pascal's Triangle:\n";
    for (int n = 0; n <= 7; n++) {
        for (int r = 0; r <= n; r++) {
            cout << nCr(n, r) << " ";
        }
        cout << "\n";
    }

    // Example: choosing 3 from 8
    cout << "\n8 choose 3 = " << nCr(8, 3) << "\n";

    // Permutation: 8P3 = 8! / 5!
    long long perm = fact[8] / fact[5];
    cout << "8 P 3 = " << perm << "\n";

    return 0;
}

Line-by-line walkthrough

1. 1. We create a global vector called 'fact' to store precomputed factorial values.
2. 2. The precompute function fills this vector: fact[0] = 1, and each fact[i] = fact[i-1] * i. This builds up 1!, 2!, 3!, etc.
3. 3. The nCr function computes combinations using the formula n! / (r! × (n-r)!). It returns 0 if r is out of range.
4. 4. In main, we call precompute(20) to calculate all factorials up to 20!. This is enough for our examples.
5. 5. We print Pascal's Triangle by looping through rows 0 to 7. For each row n, we print nCr(n, r) for r from 0 to n.
6. 6. We compute 8 choose 3 = 56, meaning there are 56 ways to pick 3 items from 8 when order doesn't matter.
7. 7. For permutations (8P3), we compute 8! / 5! = 336. This counts arrangements where order matters.
8. 8. The code keeps things simple with plain division. For CP contests with large numbers, you'd use modular arithmetic instead.

Spot the bug

#include <bits/stdc++.h>
using namespace std;

long long factorial(int n) {
    long long result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

long long nCr(int n, int r) {
    return factorial(n) / factorial(r) / factorial(n - r);
}

int main() {
    // How many ways to choose 2 from 5?
    cout << "5C2 = " << nCr(5, 2) << "\n";
    // How many ways to choose 3 from 30?
    cout << "30C3 = " << nCr(30, 3) << "\n";
    // How many ways to choose 5 from 25?
    cout << "25C5 = " << nCr(25, 5) << "\n";
    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Counting Principles and Combinatorics (YouTube)
• Combinatorics — CP-Algorithms (CP-Algorithms)
• Combinatorics Problems on Codeforces (Codeforces)