Let $t\_1,t\_2,\dots,t\_k$ be non-negative integers. Can the following sum
$$f\_k(t\_1,t\_2,\dots,t\_k):=\sum\_{j\_1=0}^{t\_1} \sum\_{j\_2=0}^{t\_2+j\_1} \sum\_{j\_3=0}^{t\_2+j\_2} \dots \sum\_{j\_k=0}^{t\_k+j\_{k-1}} 1$$
be explicitly expressed as a polynomial in $t\_1,t\_2,\dots,t\_k$ or via known combinatorial entities?


We surely have a recurrence formula:
$$f\_{k+1}(t\_1,t\_2,\dots,t\_{k+1}) = \sum\_{j=0}^{t\_1} f\_k(j+t\_2,\dots,t\_{k+1}),$$
which does not seem to easily unroll.


Just in case, first few terms are
\begin{split}
f\_0 &= 1,\\
f\_1(t\_1) &= 1+t\_1,\\
f\_2(t\_1,t\_2) &= (1+t\_1)(1+t\_2) + \frac{t\_1(1+t\_1)}2,\\
f\_3(t\_1,t\_2,t\_3) &= \left[ (1+t\_1)(1+t\_2) + \frac{t\_1(1+t\_1)}2 \right](1+t\_3) + \frac{t\_2(1+t\_2)}2 + \frac{3t\_2^2 + 6t\_2 + 2}6t\_1 + \frac{1+t\_2}2t\_1^2 + \frac16t\_1^3.
\end{split}




---


**UPDATED.** Billy Joe found that
$$f\_k(n,d,d,\dots, d) = \frac{n+1}k \binom{n+k(d+1)}{k-1}.$$
In particular, at $f\_k(1,1,\dots,1)$ gives $(k+1)$-st Catalan number.



Explicit expression for recursive sums
Claim: The iterated sum $f\_k(t\_1,\ldots,t\_k)$ counts the number of elements the interval $[\emptyset,\lambda]$ of Young's lattice, where $\lambda = (\lambda\_1,\lambda\_2,\ldots,\lambda\_k)$ is the partition determined by $\lambda\_{k-i+1} = t\_1 + \cdots + t\_i$. Equivalently, the function $f\_k$ counts the number of subdiagrams of $\lambda$.


For an arbitrary partition $\lambda$, we have
$$|[\emptyset,\lambda]| = \text{det} \left[\binom{\lambda\_i + 1}{i-j+1}\right]\_{1 \leq i,j \leq k}$$
which is a result due to P. A. MacMahon. The answer to Exercise 149 in Chapter 3 of [Stanley's Enumerative Combinatorics, volume 1, 2nd edition](https://math.mit.edu/%7Erstan/ec/ec1/) provides a good reference of references for this result, with various extensions and specializations, including some of the results mentioned in the comments. For a short visual proof using Lindström-Gessel-Viennot, see [Ciucu -
A short conceptual proof of Narayana's path-counting formula](https://arxiv.org/abs/1602.02085).


If the claim is true, MacMahon's result implies
$$\sum\_{j\_1=0}^{t\_1}\sum\_{j\_2=0}^{t\_2+j\_1}\cdots\sum\_{j\_k=0}^{t\_k+j\_{k-1}} = \text{det} \left[\binom{t\_1 + \cdots + t\_{k - i + 1} + 1}{i-j+1}\right]\_{1 \leq i,j \leq k}$$
which implies $f\_k(t\_1,\ldots,t\_k)$ is a polynomial in $t\_1,\ldots,t\_k$.


Note that $f\_k(t\_1,\ldots,t\_k)$ counts the number of $(j\_1,\ldots,j\_k)$ such that $0 \leq j\_1 \leq t\_1$ and $0 \leq j\_{i+1} \leq j\_i + t\_{i+1}$ for $i \geq 1$. To establish the claim, it suffices to find a bijection between the set of $\mu \subseteq \lambda$ and the set of tuples satisfying the above constraints.


Sketch: Map $\mu \subseteq \lambda$ to $(j\_1,\ldots,j\_k)$, where $j\_i = \lambda\_{k-i+1} - \mu\_{k-i+1}$. The visual interpretation is that each $j\_i$ measures the distance between the walls of the $i$-th row from the bottom of the Young diagrams (English convention) for $\mu$ and $\lambda$. The $t\_i$ specify how many boxes are added to the diagram for $\lambda$ in moving from the $(i-1)$-st row from the bottom to the $i$-th row. The constraints express the fact that in going from bottom to top in the diagram, the distance between walls increases by at most $t\_i$. For a more direct definition chase, note that $\lambda\_{k-i} - \lambda\_{k-i+1} = t\_{i+1}$. Since $\mu$ is a partition, we have $\mu\_{k-i+1} - \mu\_{k-i} \leq 0$. Combining the definitions and inequalities gives $j\_{i+1} \leq j\_i + t\_{i+1}$.


