HMMT 2021 T4

Let $k$ and $n$ be positive integers and let

$$S=\left\{\left(a_{1}, \ldots, a_{k}\right) \in \mathbb{Z}^{k} \mid 0 \leq a_{k} \leq \cdots \leq a_{1} \leq n, a_{1}+\cdots+a_{k}=k\right\}$$

Determine, with proof, the value of

$$\sum_{\left(a_{1}, \ldots, a_{k}\right) \in S}\binom{n}{a_{1}}\binom{a_{1}}{a_{2}} \cdots\binom{a_{k-1}}{a_{k}}$$

in terms of $k$ and $n$, where the sum is over all $k$-tuples $\left(a_{1}, \ldots, a_{k}\right)$ in $S$.