i. Counting Fundamentals

The basic counting rules, binomial coefficients and how to compute them, stars and bars with bounds, permutation tools (inverse, cycles, ranking), and the twelvefold way. Binomial coefficients mod a prime come from Comb and mint in Modular Arithmetic; identities are in Binomial Identities, inclusion–exclusion and derangements in Inclusion–Exclusion, Catalan numbers in Catalan and Lattice Paths, Stirling, Bell and partition numbers in Stirling, Bell and Partitions, symmetry counting in Burnside and Pólya, generating functions in Generating Functions.

Rule	Statement
sum rule	disjoint alternatives add
product rule	independent stages multiply (the number of choices at each stage must not depend on earlier choices)
bijection	equal counts if there is a bijection; the core of most clever counts
double counting	count one set two ways (rows vs columns, pairs vs incidences)
complement	count the opposite and subtract; with several conditions, inclusion–exclusion
pigeonhole	$N$ objects in $k$ boxes: some box has $\geq ⌈ N / k ⌉$ : Pigeonhole Puzzles

Object	Count
arrangements of $n$ distinct objects	$n!$
ordered selections of $r$ of $n$ (permutations)	$P (n, r) = n^{\underline{r}} = \frac{n !}{( n - r )!}$
subsets of size $r$ (combinations, $^{n} C_{r}$ )	$(r n) = \frac{n !}{r ! ( n - r )!}$
arrangements of a multiset with multiplicities $k_{1}, \dots, k_{m}$	multinomial $(k _{1} , \dots , k _{m} n) = \frac{n !}{k _{1} ! \dots k _{m} !}$
multisets of size $r$ from $n$ types	$(r n + r - 1)$ (stars and bars)
words of length $r$ over $n$ letters	$n^{r}$
subsets of an $n$ -set	$2^{n}$

Pascal’s rule $(r n) = (r - 1 n - 1) + (r n - 1)$ gives an $O (n^{2})$ table without inverses (any modulus); $(0 n) = (n n) = 1$ , $(r n) = (n - r n)$ , $\sum_{r} (r n) = 2^{n}$ , and the binomial theorem $(x + y)^{n} = \sum_{r} (r n) x^{n - r} y^{r}$ .

Computing $(r n)$	Method	Cost
$n \leq 5000$ , any modulus	Pascal table	$O (n^{2})$
$n \leq 1 0^{7}$ , prime modulus $> n$	factorials and inverse factorials (`Comb`)	$O (n)$ once, $O (1)$ per query
huge $n$ , small $r$ , prime modulus $> r$	falling factorial $n^{\underline{r}} / r!$	$O (r)$
$n \geq p$ for a small prime $p$	Lucas’s theorem: Factorials mod p	$O (lo g_{p} n)$
composite modulus	CRT over prime powers (Granville), or Pascal
exact values	`__int128` up to $(65 130)$ , `unsigned long long` up to $(33 67)$

vector<vector<ll>> pascalTable(int n, ll mod) {           // C[i][j] mod any modulus, O(n^2)
    vector<vector<ll>> C(n + 1, vector<ll>(n + 1, 0));
    for (int i = 0; i <= n; i++) { C[i][0] = 1 % mod; for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod; }
    return C;
}
 
mint binomLarge(ll n, int r) {                            // C(n, r) for huge n, r < modulus
    if (r < 0 || n < r) return 0;
    mint num = 1, den = 1;
    for (int i = 0; i < r; i++) num *= mint(n - i), den *= mint(i + 1);
    return num / den;
}

Proof: the formulas, Pascal's rule and the binomial theorem

Permutations: the first position has $n$ choices, the next $n - 1$ , and so on (product rule): $n^{\underline{r}}$ . Combinations: each $r$ -subset gives $r!$ ordered selections, so $(r n) = \frac{n ^{\underline{r}}}{r !}$ . Multinomial: the $n!$ arrangements of distinct labelled copies map $k_{1}! \dots k_{m}!$ to one arrangement of the multiset (permute equal copies). Pascal: an $r$ -subset of ${1.. n}$ either contains $n$ ( $(r - 1 n - 1)$ ways) or not ( $(r n - 1)$ ). Binomial theorem: expanding $(x + y)^{n}$ , a term chooses $y$ from $r$ of the $n$ factors and $x$ from the others, in $(r n)$ ways. Large $n$ : $(r n) = \frac{n ( n - 1 ) \dots ( n - r + 1 )}{r !}$ is exact over the integers, and $r!$ is invertible modulo a prime $> r$ . Checked: the Pascal table against Comb and binomLarge against exact values.

Stars and bars, with bounds

$n$ identical items into $k$ distinguishable bins: $(k - 1 n + k - 1)$ with empty bins allowed, $(k - 1 n - 1)$ with every bin non-empty; equivalently non-negative (positive) integer solutions of $x_{1} + \dots + x_{k} = n$ . With upper bounds $x_{i} \leq a_{i}$ , inclusion–exclusion over the set $S$ of variables forced above their bound:
$# {x : \sum x_{i} = s, 0 \leq x_{i} \leq a_{i}} = \sum_{S} (- 1)^{∣ S ∣} (n - 1 s - \sum _{i \in S} ( a _{i} + 1 ) + n - 1) .$
With equal bounds $l \leq x_{i} \leq r$ the sum collapses to $O (n)$ terms; with individual bounds and $s$ up to $1 0^{18}$ , the binomial is a polynomial of degree $n - 1$ in $m = s - \sum$ , so a meet in the middle over the two halves of $S$ (sorted by sum, with prefix sums of $sign \cdot y^{j}$ ) evaluates all pairs with $m \geq 0$ at once: $O (2^{n /2} n^{2})$ for $n \leq 40$ .

mint countBoundedUniform(int n, ll s, ll l, ll r) {        // #x in [l, r]^n with sum s, O(n)
    if (n == 0) return s == 0 ? 1 : 0;
    s -= (ll)n * l; ll w = r - l + 1;
    if (s < 0 || w <= 0) return 0;
    mint res = 0, cnk = 1;                                 // C(n, j)
    for (int j = 0; j <= n; j++) {
        if (j) cnk = cnk * mint(n - j + 1) / mint(j);
        ll m = s - (ll)j * w; if (m < 0) break;
        mint term = cnk * binomLarge(m + n - 1, n - 1);
        res += j % 2 ? -term : term;
    }
    return res;
}
 
mint countBoundedBrute(const vector<ll>& a, ll s) {        // 0 <= x_i <= a_i, O(2^n n)
    int n = sz(a); if (n == 0) return s == 0 ? 1 : 0;
    mint res = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        ll m = s; for (int i = 0; i < n; i++) if (mask >> i & 1) m -= a[i] + 1;
        if (m < 0) continue;
        mint term = binomLarge(m + n - 1, n - 1);
        res += __builtin_popcount(mask) % 2 ? -term : term;
    }
    return res;
}
 
mint countBoundedIndividual(const vector<ll>& a, ll s) {   // meet in the middle, O(2^(n/2) n^2), n <= ~40
    int n = sz(a); if (n <= 1) return countBoundedBrute(a, s);
    vector<mint> c(n, 0); c[0] = 1; mint den = 1;          // P(m) = C(m + n - 1, n - 1) = sum_j c_j m^j
    for (int i = 1; i <= n - 1; i++) { for (int j = n - 1; j >= 0; j--) c[j] = c[j] * mint(i) + (j ? c[j - 1] : mint(0)); den *= mint(i); }
    for (auto& x : c) x /= den;
    auto subsetSums = [&](int from, int to) { vector<pair<ll, int>> v{{0, 1}}; for (int i = from; i < to; i++) { int k = sz(v); for (int j = 0; j < k; j++) v.push_back({v[j].first + a[i] + 1, -v[j].second}); } return v; };
    int h = n / 2; auto A = subsetSums(0, h), B = subsetSums(h, n);
    sort(all(B)); int nb = sz(B);
    vector<vector<mint>> pre(nb + 1, vector<mint>(n, 0)); // pre[k][j] = sum over the first k of B of sign * y^j
    for (int k = 0; k < nb; k++) { mint y = mint(B[k].first), p = mint(B[k].second); for (int j = 0; j < n; j++) pre[k + 1][j] = pre[k][j] + p, p *= y; }
    vector<vector<mint>> C(n, vector<mint>(n, 0)); for (int i = 0; i < n; i++) { C[i][0] = 1; for (int j = 1; j <= i; j++) C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; }
    mint res = 0;
    for (auto [x, sx] : A) {
        ll t = s - x; if (t < 0) continue;
        int k = int(upper_bound(all(B), pair<ll, int>{t, INT_MAX}) - B.begin()); if (k == 0) continue;
        mint T = mint(t), total = 0; vector<mint> tp(n, 1); for (int j = 1; j < n; j++) tp[j] = tp[j - 1] * T;
        for (int j = 0; j < n; j++) {                      // sum_y sign_y P(t - y), expanding (t - y)^j
            mint inner = 0;
            for (int i = 0; i <= j; i++) { mint term = C[j][i] * tp[j - i] * pre[k][i]; inner += i % 2 ? -term : term; }
            total += c[j] * inner;
        }
        res += sx > 0 ? total : -total;
    }
    return res;
}

Proof: stars and bars and the bounded versions

Stars and bars. A distribution is a row of $n$ stars and $k - 1$ bars (bin boundaries); every arrangement of these $n + k - 1$ symbols is a distribution and is determined by the bar positions: $(k - 1 n + k - 1)$ . Non-empty bins: put one item in each first, then distribute $n - k$ freely: $(k - 1 n - 1)$ .

Upper bounds. Let $A_{i}$ be the solutions with $x_{i} > a_{i}$ . In $⋂_{i \in S} A_{i}$ substitute $x_{i} = y_{i} + a_{i} + 1$ for $i \in S$ : a bijection with non-negative solutions summing to $s - \sum_{i \in S} (a_{i} + 1)$ , counted by stars and bars (0 if negative). Inclusion–exclusion over $S$ gives the formula. With equal bounds, after shifting by $l$ the term depends only on $j = ∣ S ∣$ , giving $(j n)$ copies. Meet in the middle. For $m \geq 0$ , $(n - 1 m + n - 1) = \frac{( m + 1 ) ( m + 2 ) \dots ( m + n - 1 )}{( n - 1 )!} = P (m)$ , a polynomial of degree $n - 1$ (its coefficients are built by multiplying out the factors). Split $S = S_{1} \cup S_{2}$ over the two halves; with $x = \sum_{S_{1}}$ , $y = \sum_{S_{2}}$ and $t = s - x$ , the needed sum is $\sum_{y \leq t} sign (S_{1}) sign (S_{2}) P (t - y)$ (only $m = t - y \geq 0$ contributes). Expanding $(t - y)^{j} = \sum_{i} (i j) t^{j - i} (- y)^{i}$ , the inner sums $\sum_{y \leq t} sign \cdot y^{i}$ are prefix sums over the sorted second half, found by binary search. Checked: all three against direct enumeration for small bounds, and uniform against individual with equal bounds.

Permutation toolkit

vector<int> inversePermutation(const vector<int>& p) { vector<int> inv(sz(p)); for (int i = 0; i < sz(p); i++) inv[p[i]] = i; return inv; }
vector<int> compose(const vector<int>& f, const vector<int>& g) { vector<int> r(sz(f)); for (int i = 0; i < sz(f); i++) r[i] = f[g[i]]; return r; }   // f after g
 
vector<vector<int>> cycleDecomposition(const vector<int>& p) {   // includes fixed points as 1-cycles
    int n = sz(p); vector<char> seen(n, 0); vector<vector<int>> cycles;
    for (int i = 0; i < n; i++) if (!seen[i]) { vector<int> c; for (int j = i; !seen[j]; j = p[j]) seen[j] = 1, c.push_back(j); cycles.push_back(c); }
    return cycles;
}
 
struct OrderStatFenwick {                                  // the k-th smallest remaining value of {0..n-1}
    int n; vector<int> bit;
    OrderStatFenwick(int n) : n(n), bit(n + 1, 0) { for (int i = 0; i < n; i++) add(i, 1); }
    void add(int i, int d) { for (i++; i <= n; i += i & -i) bit[i] += d; }
    int prefixCount(int i) { int s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; }   // remaining values < i
    int kth(int k) {                                       // 0-based
        int pos = 0, pw = 1; while (pw * 2 <= n) pw *= 2;
        for (; pw; pw >>= 1) if (pos + pw <= n && bit[pos + pw] <= k) pos += pw, k -= bit[pos];
        return pos;
    }
};
 
vector<int> kthPermutation(int n, ll k) {                  // 0-based k < n!, lexicographic; n <= 20
    vector<ll> f(n + 1, 1); for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i;
    OrderStatFenwick fen(n); vector<int> res(n);
    for (int i = 0; i < n; i++) { ll q = k / f[n - 1 - i]; k %= f[n - 1 - i]; int v = fen.kth((int)q); res[i] = v; fen.add(v, -1); }
    return res;
}
 
ll permutationRank(const vector<int>& p) {                 // inverse of kthPermutation (Lehmer code)
    int n = sz(p); vector<ll> f(n + 1, 1); for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i;
    OrderStatFenwick fen(n); ll rank = 0;
    for (int i = 0; i < n; i++) { rank += (ll)fen.prefixCount(p[i]) * f[n - 1 - i]; fen.add(p[i], -1); }
    return rank;
}

$O (n)$ for inverse, composition and cycles; $O (n lo g n)$ for ranking with the Fenwick tree (an array erase would cost $O (n)$ per step). Ranks fit in long long for $n \leq 20$ ; beyond that, compute the rank modulo a prime or as a big integer. Related: the order of a permutation is the lcm of its cycle lengths; its sign is $(- 1)^{n - # cycles}$ ; sorting by swaps needs $n - # cycles$ swaps (Permutation Constructions).

Proof: ranking permutations (the factorial number system)

Permutations starting with the $q$ -th smallest available value are preceded, in lexicographic order, by exactly $q \cdot (n - 1)!$ permutations (those starting with a smaller value), and among those starting with it the rest is ranked recursively among the remaining $n - 1$ values. Hence $rank = \sum_{i} c_{i} (n - 1 - i)!$ with $c_{i}$ = the number of remaining values smaller than $p_{i}$ (the Lehmer code), $0 \leq c_{i} \leq n - 1 - i$ , and every such digit sequence occurs exactly once (mixed-radix representation): kthPermutation decodes the digits and permutationRank encodes them. The Fenwick descent finds the $(k + 1)$ -th remaining value by binary lifting on prefix counts. Checked: rank and unrank are inverse for all permutations of $n \leq 7$ , and agree with next_permutation order.

The twelvefold way

Count functions $f$ from $n$ balls to $k$ boxes, balls and boxes each labelled (L) or unlabelled (U), with $f$ arbitrary, injective ( $\leq 1$ per box) or surjective ( $\geq 1$ per box). $S (n, k)$ = Stirling numbers of the second kind, $p_{k} (n)$ = partitions of $n$ into exactly $k$ parts.

balls $\to$ boxes	any	injective	surjective
L $\to$ L	$k^{n}$	$k^{\underline{n}} = k (k - 1) \dots (k - n + 1)$	$k! S (n, k)$
U $\to$ L	$(n n + k - 1)$	$(n k)$	$(k - 1 n - 1)$
L $\to$ U	$\sum_{i \leq k} S (n, i)$	$[n \leq k]$	$S (n, k)$
U $\to$ U	$\sum_{i \leq k} p_{i} (n)$	$[n \leq k]$	$p_{k} (n)$

Proof: the twelve entries

L $\to$ L: each ball independently picks a box ( $k^{n}$ ); injective picks distinct boxes in order ( $k^{\underline{n}}$ ); surjective functions are partitions of the balls into $k$ non-empty blocks ( $S (n, k)$ ) with the blocks assigned to distinct boxes ( $k!$ ). U $\to$ L: a multiset of size $n$ from $k$ boxes is stars and bars ( $(n n + k - 1)$ ); injective is a set of $n$ boxes; surjective first puts one ball in each box and distributes $n - k$ freely, $(k - 1 n - 1)$ . L $\to$ U: unlabelled boxes forget which block is which, so a function is a set partition of the balls into at most $k$ blocks ( $\sum_{i \leq k} S (n, i)$ ), exactly $k$ blocks for surjective, and injective is possible in exactly one way iff $n \leq k$ . U $\to$ U: only the multiset of box sizes remains, an integer partition of $n$ into at most $k$ parts (resp. exactly $k$ parts); injective again $[n \leq k]$ .

Recurrences and generating functions

A linear recurrence $a_{n} = c_{1} a_{n - 1} + \dots + c_{k} a_{n - k}$ has characteristic equation $x^{k} = c_{1} x^{k - 1} + \dots + c_{k}$ ; distinct roots $x_{i}$ give $a_{n} = \sum_{i} α_{i} x_{i}^{n}$ with $α_{i}$ fixed by the initial values. In practice evaluate it for huge $n$ in $O (k^{3} lo g n)$ by matrix power ( $(a_{n + 1} a_{n}) = (1110) (a_{n} a_{n - 1})$ for Fibonacci) or $O (k lo g k lo g n)$ by Bostan–Mori (Linear Recurrences, Matrix Exponentiation DP). Generating functions turn counting into algebra: Fibonacci $\frac{x}{1 - x - x ^{2}}$ , Catalan $\frac{1 - 1 - 4 x}{2 x}$ , stars and bars $\frac{1}{( 1 - x ) ^{k}}$ ; EGFs for labelled structures (permutations $\frac{1}{1 - x}$ , derangements $\frac{e ^{- x}}{1 - x}$ ); in contests they are used through polynomial multiplication (NTT mod 998244353) to compute whole sequences at once (Generating Functions).

Two classic problems

Monotone arrays (Codeforces 57C “Array”). Arrays of length $n$ with values in $1.. n$ that are non-decreasing or non-increasing: $2 (n 2 n - 1) - n$ . Kyoya and colored balls (Codeforces 553A). Balls of $k$ colours with $c_{i}$ balls of colour $i$ are drawn so that the last ball of colour $i$ comes before the last ball of colour $i + 1$ : $\prod_{i} (c _{i} - 1 S _{i} - 1)$ with $S_{i} = c_{1} + \dots + c_{i}$ .

mint monotoneArrays(int n, const Comb& cb) { return mint(2) * cb.C(2 * n - 1, n) - mint(n); }
mint kyoyaWays(const vector<int>& c, const Comb& cb) { mint res = 1; int S = 0; for (int x : c) { S += x; res *= cb.C(S - 1, x - 1); } return res; }

Proof: the two classic counts

Monotone arrays. A non-decreasing array is a multiset of size $n$ from $n$ values: $(n 2 n - 1)$ by stars and bars; non-increasing arrays are their reverses (same count); the $n$ constant arrays are both, so the union has $2 (n 2 n - 1) - n$ . Kyoya. Process colours in order. With colours $1.. i - 1$ placed ( $S_{i - 1}$ balls, in a valid order), the last ball overall among the first $S_{i}$ must be colour $i$ ; the other $c_{i} - 1$ balls of colour $i$ go anywhere among the first $S_{i} - 1$ positions: $(c _{i} - 1 S _{i} - 1)$ ways, independently of the earlier arrangement. Multiply. Both checked against brute force for small inputs.

whoashish's cp notes

Directory

i. Counting Fundamentals

Stars and bars, with bounds

Permutation toolkit

The twelvefold way

Recurrences and generating functions

Two classic problems

Graph View

Table of Contents

whoashish's cp notes

Directory

i. Counting Fundamentals

Stars and bars, with bounds

Permutation toolkit

The twelvefold way

Recurrences and generating functions

Two classic problems

Related notes

Graph View

Table of Contents