Combinatorics and Counting

Permutations/combinations, Pascal triangle, factorial precomputation, modular combinations, stars and bars, inclusion-exclusion, Catalan numbers, derangements, pigeonhole principle, Burnside's lemma overview, and generating functions introduction.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

C(n, k) mod p in O(1) after O(n) precomputation of factorials and inverse factorials (one modular exponentiation, then inv[i−1] = inv[i]·i).

Stars and bars: distributing n identical items into k boxes = C(n + k − 1, k − 1).

Catalan numbers 1, 1, 2, 5, 14, 42, … count balanced bracket strings, binary tree shapes and triangulations.

Derangements (no element in its place) satisfy D(n) = (n − 1)(D(n−1) + D(n−2)); D(n)/n! tends to 1/e.

Burnside's lemma: the number of distinct objects under a symmetry group is the average number of objects fixed by each symmetry. Generating functions encode sequences as power series: the coefficient of xⁿ in 1/(1−x)(1−x²)(1−x⁵) counts ways to pay n with coins 1, 2, 5.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1'000'000'007;

ll power(ll b, ll e) { ll r = 1; b %= MOD; while (e) { if (e & 1) r = r * b % MOD; b = b * b % MOD; e >>= 1; } return r; }

int main() {
    int N = 1'000'000;
    vector<ll> fact(N + 1), inv(N + 1);
    fact[0] = 1; for (int i = 1; i <= N; ++i) fact[i] = fact[i - 1] * i % MOD;
    inv[N] = power(fact[N], MOD - 2);                              // one exponentiation, then walk down
    for (int i = N; i > 0; --i) inv[i - 1] = inv[i] * i % MOD;
    auto C = [&](int n, int k) { return k < 0 || k > n ? 0 : fact[n] * inv[k] % MOD * inv[n - k] % MOD; };
    cout << "C(10, 3) = " << C(10, 3) << ", C(1000000, 500000) mod p = " << C(1000000, 500000) << '\n';

    // Pascal's triangle agrees with the factorial formula
    vector<vector<ll>> P(31, vector<ll>(31, 0));
    for (int n = 0; n <= 30; ++n) { P[n][0] = 1; for (int k = 1; k <= n; ++k) P[n][k] = (P[n - 1][k - 1] + P[n - 1][k]) % MOD; }
    bool ok = true; for (int n = 0; n <= 30; ++n) for (int k = 0; k <= n; ++k) ok &= P[n][k] == C(n, k);
    cout << "Pascal's rule matches n!/(k!(n-k)!) for n <= 30: " << boolalpha << ok << '\n';

    cou
…

C(10, 3) = 120, C(1000000, 500000) mod p = 996692777
Pascal's rule matches n!/(k!(n-k)!) for n <= 30: true
stars and bars: ways to put 10 identical balls into 4 boxes = C(13, 3) = 286
Catalan numbers C(2n,n)/(n+1): 1 1 2 5 14 42 132 429 1430 4862 16796
derangements D(n) for n = 0..10: 1 0 1 2 9 44 265 1854 14833 133496 1334961
D(6) by enumerating all 720 permutations: 265
binary necklaces of length 6 up to rotation (Burnside): 14

Quiz

? Ways to distribute 10 identical balls into 4 distinct boxes?
+ C(13, 3) = 286 :: Stars and bars: C(n + k − 1, k − 1).
- 4^10 :: That is for distinct balls.
- C(10, 4) :: No.
- 10! / 4! :: No.

? Why precompute inverse factorials from inv[N] downward?
+ One modular exponentiation, then inv[i−1] = inv[i]·i — O(N) total instead of N exponentiations :: Fast precomputation.
- Because Fermat only works for large numbers :: No.
- To avoid overflow :: Not the reason.
- It is required by Pascal's rule :: No.

? Which sequences does the Catalan sequence count? (select all that apply)
+ Balanced strings of n bracket pairs :: Classic.
+ Shapes of binary trees with n nodes :: Classic.
- Subsets of an n-set :: That is 2ⁿ.
+ Triangulations of a convex polygon with n + 2 sides :: Classic.