Combinations with Repetition and the Stars and Bars Method
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: ...