## Table of Contents

ResourcesBinomial CoefficientsMethod 1: Pascal's Triangle (Dynamic Programming) - $\mathcal{O}(n^2)$Method 2: Factorial Definition (Modular Inverses) - $\mathcal{O}(n + \log MOD)$Solution - Binomial CoefficientsDerangementsMethod 1: Principle of Inclusion-ExclusionMethod 2: Dynamic ProgrammingCatalan NumbersApplicationsImplementationStars and BarsExplanationImplementationProblems# Combinatorics

Authors: Jesse Choe, Aadit Ambadkar, Dustin Miao, Mihnea Brebenel

How to count.

## Table of Contents

ResourcesBinomial CoefficientsMethod 1: Pascal's Triangle (Dynamic Programming) - $\mathcal{O}(n^2)$Method 2: Factorial Definition (Modular Inverses) - $\mathcal{O}(n + \log MOD)$Solution - Binomial CoefficientsDerangementsMethod 1: Principle of Inclusion-ExclusionMethod 2: Dynamic ProgrammingCatalan NumbersApplicationsImplementationStars and BarsExplanationImplementationProblemsIf you've never encountered any **combinatorics** before, AoPS is a good place
to start.

Resources | ||||
---|---|---|---|---|

AoPS | practice problems, set focus to Counting and Probability. | |||

AoPS | good book |

## Resources

Resources | ||||
---|---|---|---|---|

CPH | module is based off of this | |||

cp-algo | ||||

HE | teaches fundamental combinatorics with a practice problem at the end | |||

AoPS | teaches basic combinatorics concepts | |||

AoPS | teaches more advanced combinatorics concepts | |||

CF | a good blog about the expected value | |||

CF | a good blog about the inclusion-exclusion principle |

If you prefer watching videos instead, here are some options:

Resources | ||||
---|---|---|---|---|

YouTube | playlist by mathemaniac | |||

YouTube | lectures 16-23 | |||

YouTube | Errichto video regarding expected value and sums of subsets |

## Binomial Coefficients

Focus Problem – try your best to solve this problem before continuing!

The **binomial coefficient** $\binom{n}{k}$ (pronounced as "$n$ choose $k$" or
sometimes written as ${}_nC_k$) represents the number of ways to choose a subset
of $k$ elements from a set of $n$ elements. For example, $\binom{4}{2} = 6$,
because the set $\{1,2,3,4\}$ has $6$ subsets of $2$ elements:

There are two ways to calculate binomial coefficients:

### $\mathcal{O}(n^2)$

Method 1: Pascal's Triangle (Dynamic Programming) -Binomial coefficients can be recursively calculated as follows:

The intuition behind this is to fix an element $x$ in the set and choose $k − 1$ elements from $n − 1$ elements if $x$ is included in the set or choose $k$ elements from $n − 1$ elements, otherwise.

The base cases for the recursion are:

because there is always exactly one way to construct an empty subset and a subset that contains all the elements.

This recursive formula is commonly known as Pascal's Triangle.

A naive implementation of this would use a recursive formula, like below:

C++

/** @return nCk mod p using naive recursion */int binomial(int n, int k, int p) {if (k == 0 || k == n) { return 1; }return (binomial(n - 1, k - 1, p) + binomial(n - 1, k, p)) % p;}

Java

/** @return nCk mod p using naive recursion */public static int binomial(int n, int k, int p) {if (k == 0 || k == n) { return 1; }return (binomial(n - 1, k - 1, p) + binomial(n - 1, k, p)) % p;}

Python

def binomial(n: int, k: int, p: int) -> int:""":return: nCk mod p using naive recursion"""if k == 0 or k == n:return 1return (binomial(n - 1, k - 1, p) + binomial(n - 1, k, p)) % p

Additionally, we can optimize this from $\mathcal{O}(2^n)$ to $\mathcal{O}(n^2)$ using dynamic programming (DP) by caching the values of smaller binomials to prevent recalculating the same values over and over again. The code below shows a bottom-up implementation of this.

C++

/** @return nCk mod p using dynamic programming */int binomial(int n, int k, int p) {// dp[i][j] stores iCjvector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));// base cases described abovefor (int i = 0; i <= n; i++) {/** i choose 0 is always 1 since there is exactly one way* to choose 0 elements from a set of i elements

Java

/** @return nCk mod p using dynamic programming */public static int binomial(int n, int k, int p) {// dp[i][j] stores iCjint[][] dp = new int[n + 1][k + 1];// base cases described abovefor (int i = 0; i <= n; i++) {/** i choose 0 is always 1 since there is exactly one way* to choose 0 elements from a set of i elements

Python

def binomial(n: int, k, p):""":return: nCk mod p using dynamic programming"""# dp[i][j] stores iCjdp = [[0] * (k + 1) for _ in range(n + 1)]# base cases described abovefor i in range(n + 1):"""i choose 0 is always 1 since there is exactly one wayto choose 0 elements from a set of i elements

### $\mathcal{O}(n + \log MOD)$

Method 2: Factorial Definition (Modular Inverses) -Define $n!$ as $n \times (n - 1) \times (n - 2) \times \ldots 1$. $n!$ represents the number of permutations of a set of $n$ elements. See this AoPS Article for more details.

Another way to calculate binomial coefficients is as follows:

Recall that $\binom{n}{k}$ also represents the number of ways to choose $k$ elements from a set of $n$ elements. One strategy to get all such combinations is to go through all possible permutations of the $n$ elements, and only pick the first $k$ elements out of each permutation. There are $n!$ ways to do so. However, note the the order of the elements inside and outside the subset does not matter, so the result is divided by $k!$ and $(n − k)!$.

Since these binomial coefficients are large, problems typically require us to
output the answer modulo a large prime $p$ such as $10^9 + 7$. Fortunately, we
can use modular inverses to divide $n!$ by $k!$ and $(n - k)!$
modulo $p$ for any prime $p$. Computing inverse factorials **online** can be
very time costly. Instead, we can **precompute** all factorials in
$\mathcal{O}(n)$ time and inverse factorials in $\mathcal{O}(n + \log MOD)$.
First, we compute the modular inverse of the largest factorial using binary
exponentiation. For the rest, we use the fact that $(n!)^{-1} \equiv (n!)^{-1}\times (n+1)^{-1} \times (n+1) \equiv ((n+1)!)^{-1}\times (n+1)$. See
the code below for the implementation.

C++

const int MAXN = 1e6;long long fac[MAXN + 1];long long inv[MAXN + 1];/** @return x^n modulo m in O(log p) time. */long long exp(long long x, long long n, long long m) {x %= m; // note: m * m must be less than 2^63 to avoid ll overflowlong long res = 1;while (n > 0) {

Java

import java.util.*;public class BinomialCoefficients {private static final int MAXN = (int)1e6;private static long[] fac = new long[MAXN + 1];private static long[] inv = new long[MAXN + 1];/** @return x^n modulo m in O(log p) time. */private static long exp(long x, long n, long m) {x %= m; // note: m * m must be less than 2^63 to avoid ll overflow

Python

MAXN = 10**6fac = [0] * (MAXN + 1)inv = [0] * (MAXN + 1)def exp(x: int, n: int, m: int) -> int:""":return: x^n modulo m in O(log p) time."""x %= m # note: m * m must be less than 2^63 to avoid ll overflowres = 1

### Solution - Binomial Coefficients

The first method for calculating binomial factorials is too slow for this problem since the constraints on $a$ and $b$ are $(1 \leq b \leq a \leq 10^6)$ (recall that the first implementation runs in $\mathcal{O}(n^2)$ time complexity). However, we can use the second method to answer each of the $n$ queries in constant time by precomputing factorials and their modular inverses.

C++

#include <iostream>using namespace std;using ll = long long;const int MAXN = 1e6;const int MOD = 1e9 + 7;ll fac[MAXN + 1];ll inv[MAXN + 1];

Java

import java.io.*;import java.util.*;public class BinomialCoefficients {private static final int MAXN = (int)1e6;private static final int MOD = (int)1e9 + 7;private static long[] fac = new long[MAXN + 1];private static long[] inv = new long[MAXN + 1];public static void main(String[] args) {

Python

MAXN = 10**6MOD = 10**9 + 7fac = [0] * (MAXN + 1)inv = [0] * (MAXN + 1)Code Snippet: Counting Functions (Click to expand)

## Derangements

Focus Problem – try your best to solve this problem before continuing!

The number of derangements of $n$ numbers, expressed as $!n$, is the number of permutations such that no element appears in its original position. Informally, it is the number of ways $n$ hats can be returned to $n$ people such that no person recieves their own hat.

### Method 1: Principle of Inclusion-Exclusion

Suppose we had events $E_1, E_2, \dots, E_n$, where event $E_i$ corresponds to person $i$ recieving their own hat. We would like to calculate $n! - \lvert E_1 \cup E_2 \cup \dots \cup E_n \rvert$.

We subtract from $n!$ the number of ways for each event to occur; that is, consider the quantity $n! - \lvert E_1 \rvert - \lvert E_2 \rvert - \dots - \lvert E_n \rvert$. This undercounts, as we are subtracting cases where more than one event occurs too many times. Specifically, for a permutation where at least two events occur, we undercount by one. Thus, add back the number of ways for two events to occur. We can continue this process for every size of subsets of indices. The expression is now of the form:

For a set size of $k$, the number of permutations with at least $k$ indicies can be computed by choosing a set of size $k$ that are fixed, and permuting the other indices. In mathematical terms:

Thus, the problem now becomes computing

which can be done in linear time.

C++

#include <atcoder/modint>#include <bits/stdc++.h>using namespace std;using mint = atcoder::modint;int main() {int n, m;cin >> n >> m;mint::set_mod(m);

Java

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();long c = 1;for (int i = 1; i <= n; i++) {

Python

n, m = map(int, input().split())c = 1for i in range(1, n + 1):c = (c * i) + (-1 if i % 2 == 1 else 1)c %= mc += mc %= mprint(c, end=" ")print()

### Method 2: Dynamic Programming

Suppose person 1 recieved person $i$'s hat. There are two cases:

- If person $i$ recieves person 1's hat, then the problem is reduced to a subproblem of size $n - 2$. There are $n - 1$ possibilities for $i$ in this case, so we add to the current answer $(n - 1)\cdot !(n - 2)$.
- If person $i$ does not recieve person 1's hat, then we can reassign person 1's hat to be person $i$'s hat (if they recieved person 1's hat, then this would become first case). Thus, this becomes a subproblems with size $n - 1$, are there $n - 1$ ways to choose $i$.

Thus, we have

which can be computed in linear time with a simple DP. The base cases are that $!0 = 1$ and $!1 = 0$.

C++

#include <atcoder/modint>#include <bits/stdc++.h>using namespace std;using mint = atcoder::modint;int main() {int n, m;cin >> n >> m;mint::set_mod(m);

Java

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int a = 1;int b = 0;

Python

n, m = map(int, input().split())a, b = 1, 0print(0, end=" ")for i in range(2, n + 1):c = (i - 1) * (a + b) % mprint(c, end=" ")a, b = b, cprint()

## Catalan Numbers

Resources | ||||
---|---|---|---|---|

cp-algo | Well documented article. |

The Catalan numbers are a sequence of positive integers that can be very useful in counting problems in combinatorics. The $n$-th Catalan can be expressed as following using binomial coeffiecients:

They also have the recurrence formula

which can also be expressed as

The first $5$ Catalan numbers are

n | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|

$C_n$ | 1 | 1 | 2 | 5 | 14 | 42 |

### Applications

The Catalan numbers can be used to represent a wide variety of things.

For example, $C_n$ is equal to the number of valid parenthesis expressions of length $2n$. Take, for instance, $C_3=5$:

`()()()`

`(())()`

`()(())`

`((()))`

`(()())`

It's also equal to the number of full binary trees with $n+1$ leaves. The following image shows the $5$ binary trees with $4$ leaves:

$C_n$ is also the number of monotonic lattice paths along the edges of a $n \times n$ grid that don't pass above the diagonal. The paths start in the lower left corner and ends in the upper right corner.

For example, there are $C_4=14$ paths in a $4 \times 4 grid$:

The next two examples are a bit more niche, but they're still interesting to think about.

Consider a convex polygon with $n+2$ sides divided into $n$ triangles by connecting vertices with non-intersecting lines. The number of different ways to divide the polygon in this way is equal to $C_n$.

Here's the particular case for $n=3$ in which we have $C_3=5$:

$C_n$ is also equal to the number of mountain ranges of length $2n$ consisting of $n$ upstrokes and $n$ downstrokes.

Focus Problem – try your best to solve this problem before continuing!

### Implementation

**Time Complexity:** $\mathcal{O}(N^2)$

C++

#include <iostream>using namespace std;const int MOD = 1e6;const int MAX_N = 2e3;int main() {int catalan[MAX_N][MAX_N];for (int i = 1; i < MAX_N; i++) {

## Stars and Bars

Resources | ||||
---|---|---|---|---|

cp-algo | ||||

Medium | Well documented article. |

Stars and Bars is a useful method in combinatorics that involves grouping indistinguishable objects into distinguishable boxes. The number ways to put $n$ indistinguishable objects into $k$ distinguishable boxes is:

The second binomial coefficient from above can be derived from the property of binomial coefficients: $\binom{n}{k}=\binom{n}{n-k}$.

Let's take a look at a particular example for $n=3$ and $k=2$ that has $4$ possibilities. As the name implies, the visualization is usually done with stars separated into groups by bars:

As you've probably noticed, there can be empty boxes - when we put all the stars in the first or second box. There may be cases in
which the all the boxes should be non-empty. In that case, the number of ways to put $n$ indistinguishable objects into $k$
distinguishable **non-empty** boxes is: $\binom{n-1}{k-1}$

Focus Problem – try your best to solve this problem before continuing!

### Explanation

For this problem we should think the other way around: let's say that the $k$ colors from which we choose are in fact boxes and instead of choosing $n$ marbles we put them in the respective boxes. The problem has the restriction that we should pick at least one marble of all kinds, which means in our new perspective that all the boxes should be non-empty. Thus, the answer is obtained by the second formula: $\binom{n-1}{k-1}$

### Implementation

**Time Complexity:** $\mathcal(O)(T \cdot K)$

C++

#include <iostream>using namespace std;long long comb(int n, int k) {if (k > n - k) { k = n - k; }long long ans = 1;for (int i = 0; i < k; i++) { ans = ans * (n - i) / (i + 1); }return ans;}

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CSES | Easy | ## Show TagsCombinatorics | |||

CSES | Easy | ## Show TagsCombinatorics | |||

CF | Easy | ## Show TagsCombinatorics | |||

CF | Easy | ## Show TagsBinary Search, Combinatorics | |||

Bronze | Easy | ## Show TagsCombinatorics | |||

Bubble Cup | Normal | ## Show TagsCombinatorics | |||

CF | Normal | ## Show TagsCombinatorics | |||

AC | Normal | ## Show TagsCombinatorics | |||

Gold | Normal | ## Show TagsCombinatorics | |||

Gold | Normal | ## Show TagsBitset, PIE | |||

CF | Normal | ## Show TagsCombinatorics, DP | |||

Gold | Normal | ## Show TagsCombinatorics, Prefix Sums | |||

CF | Hard | ## Show TagsCombinatorics, DP | |||

Gold | Insane | ## Show TagsBinary Search, Combinatorics, Math, Probability |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!