Hi everyone!

Today I want to write about the Gale-Ryser Theorem and some of its applications.

Gale-Ryser Theorem

We have an array of $$$n$$$ non-negative integers $$$a_1, a_2, \ldots, a_n$$$ and $$$m$$$ positive integers $$$b_1, b_2, \ldots, b_m$$$ up to $$$n$$$. The array $$$b$$$ is a sequence of operations, in $$$i$$$-th operation we need to decrease $$$b_i$$$ positions by $$$1$$$, formally pick $$$b_i$$$ unique indices $$$j_1, j_2, \ldots, j_{b_i}$$$ and decrease $$$a_{j_p}$$$ by $$$1$$$ for $$$1 \le p \le b_i$$$. We want to know if it's possible to have all $$$a_i \ge 0$$$ after the operations.

Without loss of generality $$$b_1 \ge b_2 \ldots \ge b_m$$$. The Theorem says that it's possible iff $$$\sum \limits_{i=1}^k \min(a_i, k) \ge \sum \limits_{j=1}^k b_j$$$ for $$$\forall 1 \le k \le m$$$.