Algorithms / Combinatorics Interview

Least You Need to Know: Combinatorics Patterns: Choose vs Arrange, Complement Counts, and Stars and Bars

Interview counting often comes down to a modeling choice: are you choosing a set, arranging an ordered sequence, counting the easier complement, or distributing identical units across labeled bins? The hard part is recognizing which model matches the wording.

The least you need to know

Use combinations when order does not matter and permutations when it does.
Complement counting is often cleaner than counting a messy forbidden set directly.
Stars and bars counts distributions of identical items into labeled bins under clear constraints.
Repeated objects require division by duplicate factorials or a direct multiset model.
A correct counting solution starts by stating exactly what makes two outcomes different.

Key notation

C(n, k) number of `k`-element subsets of `n` distinct items

P(n, k) number of ordered length-`k` selections from `n` distinct items

x_1 + ... + x_k = n distribution model for stars and bars

Tiny worked example

If a prompt asks for a 3-person committee from 10 students, order does not matter, so choose with `C(10, 3)`.
If it asks for gold, silver, and bronze from the same 10 students, the positions differ, so order matters and you use an arrangement count.

Common mistakes

Students often compute a permutation when the output is really an unordered group.
Stars and bars applies to identical items in labeled bins, not to arbitrary arrangement problems.
Complement counting works only if the easier set is clearly defined and subtractable from the total.

How to recognize this kind of problem

The wording asks for committees, teams, or subsets rather than rankings or seatings.
The bad cases are easier to count than the good ones, suggesting a complement.
The problem distributes identical units across categories with simple lower-bound constraints.