Lesson 25 · Core algorithms

Combinatorics Basics

Combinatorics counts structured choices through permutations, combinations, recurrences, and inclusion-exclusion without enumerating every outcome.

The product and sum rules

Use the sum rule for disjoint alternatives and the product rule for sequential independent choices. If alternatives overlap, plain addition double counts; if later choices depend on earlier ones, multiply the actual number remaining at each stage.

A counting solution begins by defining one-to-one correspondence between objects and counted decisions. Formulas without that mapping are easy to apply to the wrong sample space.

Add disjoint cases
Multiply sequential choices
Build a bijection to the counted objects

Permutations and combinations

There are n! orderings of n distinct objects and n!/(n−r)! ordered selections of r. Unordered selections are C(n,r)=n!/(r!(n−r)!), because each chosen set has r! internal orders.

Repeated identical objects divide by factorials of multiplicities. Combinations with repetition use C(n+r−1,r) through stars and bars under the correct nonnegative-solution model.

Permutations care about order
Combinations quotient internal order
Repeated objects change the denominator

Key reference

Terms, operations, and practical uses

Counting choices

PermutationPermutation is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
CombinationCombination is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Product ruleProduct rule is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Binomial tools

FactorialFactorial is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Pascal recurrencePascal recurrence is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Inverse factorialInverse factorial is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Advanced counting

Inclusion-exclusionInclusion-exclusion is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Stars and barsStars and bars is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
SymmetrySymmetry is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Implementation

Pascal DP computes a binomial coefficient

n=5;r=2;dp=[[0]*(r+1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0]=1
    for j in range(1,min(i,r)+1):dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
print("C(5,2):",dp[n][r])

#include <algorithm>
#include <array>
#include <cstring>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
int main() {
    int dp[6][3]={};
    for(int i=0;i<=5;i++) {
        dp[i][0]=1;
        for(int j=1;j<=min(i,2);j++) dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
    }
    cout << "C(5,2): " << dp[5][2] << '\n';
}

class Main {
    public static void main(String[] args) {
        int[][] dp=new int[6][3];
        for(int i=0;i<=5;i++) {
            dp[i][0]=1;
            for(int j=1;j<=Math.min(i,2);j++) dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
        }
        System.out.println("C(5,2): "+dp[5][2]);
    }
}

Watch it run

Step through it

Running on C(5,2)

Output

Pascal recurrence

C(n,r)=C(n−1,r−1)+C(n−1,r): separate subsets by whether they contain one distinguished element. Boundary values C(n,0)=C(n,n)=1 make a stable O(nr) DP without division.

Symmetry C(n,r)=C(n,n−r) reduces multiplicative work. Compute multiply-then-divide carefully with exact arithmetic; intermediate overflow can occur even when the final result fits.

Include or exclude one element
Pascal DP avoids inverses
Use r=min(r,n−r)

Modular binomial coefficients

For prime modulus and n below the modulus, precompute factorials and inverse factorials for O(1) queries. Larger n or composite moduli require Lucas-type, prime-factor, or CRT methods; the simple inverse-factorial formula may fail.

Pascal DP works for any modulus within its time bound because it uses only addition. Choose by constraints and state modulus assumptions explicitly.

Inverse factorials need invertibility
Pascal addition works for composite moduli
Constraints select the method

Inclusion-exclusion and tests

For overlapping bad properties, subtract singles, add pair intersections, and alternate signs. Every object with k bad properties contributes Σ(-1)^(j+1)C(k,j)=1 to the union.

Test n=0, r=0, r>n, repeated objects, and small cases by enumeration. Distinguish choosing zero items—one empty choice—from having zero valid outcomes.

Alternate intersection signs
The empty selection is one object
Enumerate tiny cases as an oracle

A disciplined counting workflow

First label whether objects are distinct, whether order matters, whether repetition is allowed, and whether every position must be filled. Next partition into disjoint cases or construct sequential choices. Only then select factorial, binomial, stars-and-bars, or inclusion-exclusion formulas. This sequence prevents memorized formulas from overriding the actual model.

For exact large answers, use arbitrary-precision integers or cancel numerator and denominator factors with gcd before multiplication. For many modular queries, precomputation trades O(N) setup and memory for O(1) answers. For a single small r, the multiplicative product may be simpler and safer.

Use generating functions, recurrences, or DP when local restrictions couple choices and destroy a simple product. A formula is valuable only with its preconditions; include them beside the implementation so future reuse does not silently change distinctness, ordering, or repetition assumptions.

Inclusion–exclusion is best derived per object: an object belonging to k forbidden sets is counted C(k,1)−C(k,2)+…, which equals one. Therefore every object in the union contributes exactly once and every object outside contributes zero. This object-level argument prevents sign mistakes in larger formulas. Stars and bars similarly requires distinguishable positions and identical items; positivity changes the transformation by assigning one item to every box first. Test formulas against brute-force enumeration for small n, including zero boxes or items where the mathematical domain permits them. Explicit domains matter because factorial notation alone does not define invalid negative arguments. Name every counted object before manipulating a formula. A short verbal interpretation beside each term makes later audits much easier.

Classify the sample space
Derive before selecting a formula
Choose exact or modular arithmetic deliberately