Combinatorics studies how to count selections, arrangements, and cases.
In algorithms, it appears when the problem asks how many ways something can happen.
Core Idea
The main distinction is between order mattering and order not mattering. Arrangements care about order. Combinations do not.
Counting can be direct through formulas, recursive through dynamic programming, or constrained by modular arithmetic.
Usage Contract
math.comb(n, k) counts unordered selections of k items from n distinct items.
math.perm(n, k) counts ordered arrangements. Both functions assume the formula’s ordinary conditions, such as non-negative integer arguments and k <= n.
Python Example
import math
ways_to_choose = math.comb(5, 2)
arrangements = math.perm(5, 2)math.comb(5, 2) counts unordered selections. math.perm(5, 2) counts ordered arrangements.
Order Matters or Not
Choosing two people from five for a team does not care about order, so it is a combination.
Choosing a first-place and second-place winner does care about order, so it is a permutation.
This distinction often decides the formula or DP transition.
Counting Without Listing
If there are many possibilities, listing them may be impossible. Combinatorics tries to count them directly.
For example, the number of subsets of n distinct items is 2^n because each item has two choices: included or not included.
Complexity
Computing a formula can be much faster than generating all cases. But if the problem asks to output all cases, the output itself may be exponential.
Basic Counting Principles
If one independent choice has a options and another independent choice has b options, together they have a * b possibilities.
If a case can happen in one of several non-overlapping ways, add the counts for those ways.
These two ideas, product and sum, appear underneath many more advanced formulas.
Small Examples
Choosing a password with one digit and one lowercase letter gives:
10 * 26possibilities if the choices are independent.
Choosing either a red item from 3 options or a blue item from 5 options gives:
3 + 5possibilities if the categories do not overlap.
Common Confusions
Counting all cases is not the same as listing all cases. A problem may need only the count, and listing every case may be too slow.
Be careful about duplicates. Counting arrangements of repeated values requires different reasoning from counting arrangements of distinct values.
Another common mistake is multiplying choices that are not independent. If one choice changes the number of later choices, the counting argument must account for that.
When To Use It
Use combinatorics when a problem asks for number of ways, possible selections, arrangements, partitions, probability counts, or DP transitions based on choices.
Do not use a memorized formula unless the problem conditions match the formula’s assumptions.
The Main Point
Combinatorics counts possibilities without listing them. The first question is whether order matters and whether cases overlap.