Explicit expression for recursive sums

Question

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.

Answer 1

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 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.

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}$.

Answer 2

$f_k(t_1,\dots,t_k)$ is counting the number of integer points in the "Pitman-Stanley polytope" $\Pi_k(t_1,\dots,t_k)$ defined here. The notation $N(\Pi_k(\mathbf{t}))$ is used in this paper, which has the determinantal formula given by Hugh Denoncourt, as well as a combinatorial formula. The combinatorial formula is equivalent to $$ f_k(t_1,\dots,t_k)=\sum_{\mathbf{h}\in K_k} \binom{t_1+h_1}{h_1} \prod_{i=2}^k \binom{t_i+h_i-1}{h_i}, $$ where $$ K_k := \{\mathbf{h}\in\mathbb{N}^k\colon \sum_{i=1}^j h_i\geq j\ \mathrm{for\ all}\ 1\leq j\leq k-1\ \mathrm{and}\ \sum_{i=1}^k h_i=k \}. $$ The set $K_k$ has a Catalan number $C_k$ of elements.