What is the coefficient of a term in the expansion of a binomial raised to the tenth power? The binomial theorem answers in one line, with the coefficients from Pascal’s triangle. We will see the theorem and its proof by induction, the general term formula, and the identities that come from special cases.
A set with 10 elements has 1,024 subsets, and that is the sum of row 10 of Pascal’s triangle. We will see the identities of binomial coefficients: symmetry, Pascal’s rule (Stifel’s rule), and the row, column, and diagonal theorems.
At an ice cream shop with 7 flavors, there are 210 ways to order 4 scoops, repeating flavors allowed. We get there with the stars and bars method, which shows that choosing with repetition, distributing balls into boxes, and solving integer equations are the same problem.
A 4-digit password allows repetition, and that is why there are 10,000 of them: ten options in each of the four positions. The arrangement with repetition counts passwords, license plates, and RGB colors, and shows how many patterns fit in the 32 bits of a float and in the registers of an HP-11C calculator.
How many anagrams does the word MAMBEMBE have? Fewer than an 8-letter word with distinct letters would have, because swapping two equal letters does not create a new anagram. The formula discounts the repetitions by dividing by factorials, and it works for binary sequences and for shortest paths on grids.
Out of 10 friends, 3 go buy the popcorn. Only who goes matters, not the order of the choice, so there are 120 possible groups. We will see the combination formula, its symmetry, the complement method, and how to split a set into groups.
In a race with 10 athletes, the podium can be filled in 720 ways. That is an arrangement, an ordered selection of some elements of a set. We solve problems about routes, license plates, and numbers with distinct digits, with Python and SQL.
How many anagrams does the word VIRUS have? In how many ways can 5 friends sit around a table? The answers are 120 and 24, by simple and circular permutations. We will also see adjacency restrictions, the traveling salesman problem, and derangements.
With 4 math books and 3 Portuguese books, there are 7 ways to pick one book and 12 ways to pick one of each. The first count is a sum and the second is a product: these are the sum rule and the product rule, applied here to passwords, flags, answer keys, and counting divisors.
How many 8-character passwords are there? In how many ways can 10 people sit around a table? Combinatorics answers without listing every case. This is the roadmap of the series: from the counting rules to permutations, arrangements, combinations and the binomial theorem.
How many moves does it take to solve the Tower of Hanoi? The answer comes from a recurrence relation, which writes the problem in terms of itself with one disk fewer. We set up recurrences and solve them by substitution, by the characteristic equation and by the Master Theorem, used for merge sort.
Adding the sizes of two sets counts the intersection twice. The Inclusion-Exclusion Principle fixes the count, for two, three, or any number of sets. We will also see infinities of different sizes, derangements, and the Sieve of Eratosthenes.
In how many ways can you choose a valid password? What is the shortest path between two cities? These are questions of discrete mathematics. This roadmap introduces the site’s four series on the topic: sets, induction and recurrence, combinatorics, and graphs, with 28 articles.
