Combinatorics

The binomial coefficient C(n, k) is the number of ways to choose $k$ items out of $n$ when the order doesn't matter. You compute it with Pascal's triangle when $n$ is at most a few thousand, and with factorials modulo a prime when $n$ is up to 10^6. To list the choices themselves rather than count them, use backtracking.

Stars and bars counts the ways to share $n$ identical items among $k$ distinct groups, such as candies among children or the solutions of x_1 + x_2 + \dots + x_k = n in non-negative integers. It writes each sharing as a row of items and dividers, so the count becomes a binomial coefficient. If a group may hold only a limited number of items, you also need inclusion–exclusion.