Mathematics

Counting the number of valid bracket (parenthesis) sequences formed by $n$ opening brackets ( and $n$ closing brackets ) is one of the most celebrated problems in combinatorics and computer science. Whether you are parsing expressions, counting binary trees, or analyzing stack permutations, the answer is always the $n$-th Catalan number: \[ C_n = \frac{1}{n+1}\binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n+1}. \]In this post, we will formally define valid bracket sequences, build geometric intuition using lattice paths (Dyck paths), and prove the closed-form formula using André’s Reflection Principle as well as the first-return recurrence relation. ...

In combinatorics and algorithm design, a classic family of counting problems asks: How many ways can we choose $k$ items from $n$ distinct types when repetition is allowed? Equivalently, how many integer solutions exist for a linear equation under various boundary constraints? This post breaks down the Stars and Bars (also known as the dividers or balls and urns) method across three canonical scenarios: Unbounded repetition ($x_i \ge 0$) At least one of each type ($x_i \ge 1$) Lower and upper bounds ($l_i \le x_i \le u_i$) via Inclusion-Exclusion and Dynamic Programming 1. Combinations with Repetition ($x_i \ge 0$) Problem Statement Suppose we have $n$ types of items and want to select $k$ items in total, where: ...