Lesson 3

For such standard combinatorial objects as permutations and combinations, we managed to derive explicit formulas. We deliberately do not give a strict definition of an “explicit formula.” For example, a formula can be considered explicit if it involves standard arithmetic operations (addition, multiplication, exponentiation) but does not include ellipses, summation, or indexed products. The formula for the arithmetic series is a standard example of an explicit formula: \[\sum_{i \in [n]}i=1+2+3+\dotsb+n=\frac{n(n+1)}{2}.\] At the same time, the number of permutations of \(n\) elements is \(n!\). This is a short and convenient formula, but \(n!\) is just notation for a complex expression, the product of the first \(n\) numbers: \[n! = 1 \cdot 2 \cdot 3 \dotsb n = \prod_{i \in [n]}i \ .\] In this section, we will see several examples of combinatorial objects for which writing explicit formulas is challenging, while writing recurrence relations is relatively simple.