9. Consider permutations $\left(a_{0}, a_{1}, \ldots, a_{2022}\right)$ of $(0,1, \ldots, 2022)$ such that
- $a_{2022}=625$,
- for each $0 \leq i \leq 2022, a_{i} \geq \frac{625 i}{2022}$,
- for each $0 \leq i \leq 2022,\left\{a_{i}, \ldots, a_{2022}\right\}$ is a set of consecutive integers (in some order).
The number of such permutations can be written as $\frac{a!}{b!c!}$ for positive integers $a, b, c$, where $b>c$ and $a$ is minimal. Compute $100 a+10 b+c$.
Answer:
216695

Solution: Ignore the second condition for now. The permutations we seek are in bijection with the $\binom{2022}{625}$ ways to choose 625 indices $i \leq 2021$ so that $a_{i}<625$. These are in bijection with up-right lattice paths from $(0,0)$ to $(625,1397)$ in the following way: a step $(i, j) \rightarrow(i+1, j)$ indicates that $a_{i+j}=i$, while a step $(i, j) \rightarrow(i, j+1)$ indicates that $a_{i+j}=2022-j$.
Under this bijection, the second condition now becomes: for every right step $(i, j) \rightarrow(i+1, j)$, we have $i \geq \frac{625}{2022}(i+j)$, which is equivalent to $j \leq \frac{1397}{625} i$. In other words, we want to count the number of paths from $(0,0)$ to $(625,1397)$ that stay under the line $y=\frac{1397}{625} x$.
This can be counted via a standard shifting argument. Given a path from $(0,0)$ to $(625,1397)$, one can shift it by moving the first step to the end. We claim that exactly one of these cyclic shifts has the property of lying under the lines $y=\frac{1397}{625} x$. If we can show this, it follows that the answer is $\frac{2021!}{1397!625!}$, since, as $\operatorname{gcd}(2022,625)=1$, all the cyclic shifts are distinct. (It is true that the 2021 is minimal and that, given the numerator, the form of the denominator is unique. However, proving this is a bit annoying so we omit it here.)
To see that exactly one cyclic shift lies under the line, imagine extending a path infinitely in both directions in a periodic manner. A cyclic shift corresponds to taking a subset of this path between two points $P$ and $Q$ at distance 2022 along the path. Note that the condition of the path lying below the line corresponds to the infinite path lying below line $P Q$, so the unique $P, Q$ that satisfy this condition are those that lie on the highest line of slope $\frac{1397}{625}$ that touches the path. Since $\operatorname{gcd}(2022,625)=1$, these points are unique.