HMMT-Feb 2018 guts, Problem 32

How many 48-tuples of positive integers $\left(a_{1}, a_{2}, \ldots, a_{48}\right)$ between 0 and 100 inclusive have the property that for all $1 \leq i<j \leq 48, a_{i} \notin\left\{a_{j}, a_{j}+1\right\}$ ?

Solution: (With Ashwin Sah) The key idea is write the elements of the sequence in increasing order. These sets are in bijection with solutions to $d_{1}+\ldots+d_{k}=48$ and $a_{1}+\ldots+a_{k+1}=53$ with $d_{i} \geq 1, a_{i} \geq 1$ for\\ $2 \leq I \leq k$, and $a_{1}, a_{k+1} \geq 0$. Notice that there are $\left(\begin{array}{c}54 \\ k\end{array}\right)$ solutions to the second equation and then there are $\frac{48 !}{d_{1} ! \cdots d_{k} !}$ solutions for each $\left\{d_{i}\right\}$ set. Then this gives that the answer is \[ \begin{gathered} \sum_{1 \leq k \leq 48}\left(\begin{array}{c} 54 \\ k \end{array}\right) \sum_{d_{1}+\ldots+d_{k}=48} \frac{48 !}{\prod_{i=1}^{k} d_{i} !} \\ =48 !\left[x^{48}\right] \sum_{1 \leq k \leq 48}\left(e^{x}-1\right)^{k}\left(\begin{array}{c} 54 \\ k \end{array}\right) \\ =48 !\left[x^{48}\right] \sum_{0 \leq k \leq 54}\left(e^{x}-1\right)^{k}\left(\begin{array}{c} 54 \\ k \end{array}\right) \\ =48 !\left[x^{48}\right]\left(e^{x}\right)^{54} \\ =54^{48} \end{gathered} \] $\fbox{54^{48}}$.

Answer: 54^{48}