Question 52
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$.
$$
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$.