2025 AMC 12A Problem 23

The digits are distinct and drawn from $\{1, \ldots, 9\},$ and “no digit adjacent to two greater digits” means no interior digit is smaller than both neighbors. For a fixed set of $n$ digits, build the arrangement by inserting digits from largest to smallest; each new (smaller) digit must go to one of the two ends, giving $2^{n-1}$ valid arrangements. Summing over all nonempty digit subsets, $$\begin{gathered} \sum_{n=1}^{9}\binom{9}{n}2^{n-1} \\ = \frac{1}{2}\sum_{n=1}^{9}\binom{9}{n}2^{n} \\ = \frac{3^9 - 1}{2} = \frac{19682}{2} = 9841. \end{gathered}$$ Thus, the correct answer is C.