Foundations
Combinatorics Basics
Difficulty: Intermediate
How many ways can you arrange n items? How many subsets does a set of size n have? Questions like these are not idle puzzles, they are exactly the questions you have to answer to know whether a brute-force solution will run in...
Combinatorics Basics
How many ways can you arrange n items? How many subsets does a set of size n have? Questions like these are not idle puzzles, they are exactly the questions you have to answer to know whether a brute-force solution will run in milliseconds or in millennia. Combinatorics Basics gives you the counting tools that turn vague statements like "try every possibility" into precise complexity claims.
This lesson covers the four counting ideas you will rely on throughout DSA. The rule of sum and rule of product let you decompose multi-step processes and count outcomes; permutations count ordered arrangements (n! for arranging all of them, nPr for choosing r in order); combinations count unordered selections (nCr, also written as binomial coefficients); and Pascal's triangle plus a first look at basic probability tie everything together. You will see why a set of size n has 2^n subsets, why generating all permutations of an array is O(n!), and how counting principles directly produce the time complexity of backtracking algorithms.
This lesson builds on Discrete Mathematics Basics, where you formalized sets, set operations, and logic. Combinatorics is what happens when you start asking "how many?" about those sets, ordered or unordered, with or without repetition.
With the counting toolkit in place you will continue the math track in Number Theory Fundamentals, picking up primes, divisibility, and gcd, the other half of the math you need for hashing, cryptography-style problems, and modular arithmetic.
Prerequisites:
Discrete Mathematics BasicsTopics:
What You'll Learn
By the end of this lesson, you will be able to:
Apply the rule of sum and rule of product to count outcomes in multi-step processes.
Compute permutations (nPr) for ordered arrangements and explain when order matters.
Compute combinations (nCr) for unordered selections and distinguish them from permutations.
Build and interpret Pascal's triangle and connect it to binomial coefficients.
Calculate basic probabilities using the ratio of favorable to total outcomes.
Identify combinatorial patterns in algorithm complexity analysis and backtracking problems.
Why This Matters
01
Counting principles tell you the size of the search space an algorithm must explore -- this directly determines time complexity for brute-force and backtracking solutions.
02
Permutation and combination formulas appear everywhere in algorithm analysis: from the number of subsets (2^n) to the number of ways to choose k items from n (C(n,k)).
03
Understanding combinatorics is essential for probability, which underlies randomized algorithms, hashing analysis, and expected-case complexity.
04
Interview problems frequently involve counting arrangements, subsets, or paths -- you need these formulas to reason about both the problem and its complexity.
Key Terms
8 terms you'll encounter in this lesson
Permutation
An ordered arrangement of objects. The number of ways to arrange r items from n is nPr = n! / (n-r)!. Order matters: ABC and BAC are different permutations.
Combination
An unordered selection of objects. The number of ways to choose r items from n is nCr = n! / (r!(n-r)!). Order does not matter: {A,B,C} and {C,B,A} are the same combination.
Factorial
The product of all positive integers up to n, written n!. For example, 5! = 5 x 4 x 3 x 2 x 1 = 120. By convention, 0! = 1.
Rule of Product
If task A can be done in m ways and task B can be done in n ways (independently), then doing A then B can be done in m x n ways. Also called the multiplication principle.
Rule of Sum
If task A can be done in m ways and task B can be done in n ways, and the tasks are mutually exclusive, then doing A or B can be done in m + n ways. Also called the addition principle.
Binomial Coefficient
Another name for C(n, k) or 'n choose k'. It counts the number of ways to choose k items from n, and appears in the expansion of (a + b)^n.
Pascal's Triangle
A triangular array where each entry is the sum of the two entries above it. Row n contains the binomial coefficients C(n,0), C(n,1), ..., C(n,n).
Sample Space
The set of all possible outcomes of an experiment. Probability of an event = (favorable outcomes) / (total outcomes in sample space).
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"Permutations and combinations are interchangeable"
Permutations count ordered arrangements (ABC differs from BAC), while combinations count unordered selections ({A,B,C} = {C,B,A}). Always ask: does the order of selection matter? If yes, use permutations; if no, use combinations.
"0! should be 0, not 1"
By convention and mathematical necessity, 0! = 1. This is because there is exactly one way to arrange zero objects (do nothing). It also makes formulas like C(n,0) = n! / (0! x n!) = 1 work correctly.
"C(n, k) and C(n, n-k) are different values"
They are always equal: C(n, k) = C(n, n-k). Choosing k items to include is the same as choosing n-k items to exclude. This symmetry is visible in Pascal's triangle.
"The number of subsets of a set with n elements is n^2"
The number of subsets is 2^n, not n^2. Each element has 2 independent choices (include or exclude), so the total is 2 x 2 x ... x 2 = 2^n by the rule of product.