# Explicit expression for recursive sums

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.

• The equal arguments case looks like it should also give the Ehrhart polynomial of some lattice polytope. May 9 at 2:20
• FWIW it seems that $f_k(1,2,3,\ldots,k-2,k-2,k)=a(k+1)$, where $a(k)$ is A107877. May 10 at 17:32
• @BillyJoe: Nice catch! In fact, it is stated there as conjecture by Benedict W. J. Irwin. May 10 at 17:49
• Are you sure about A016121? Apparently $f_k(n,d,d,\ldots,d,d)=\frac{n+1}{k}\binom{n+k(d+1)}{k-1}$. May 10 at 21:08
• Irwin's conjecture on A107877 is equivalent to the earlier comment by Joerg Arndt, Apr 30 2011, which doesn't qualify it as a conjecture. May 11 at 7:19

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