Return to 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}

ADDED. In the case of equal arguments, the values $\big(f_k(t,t,\dots,t)\big)_{k\geq 0}$ apparently represent the row sums of the $t$-th power of the matrix $T$ defined in OEIS A097712 and also the $t$-th column of table in OEIS A125860.

In particular, $\big(f_k(1,1,\dots,1)\big)_{k\geq 0}$ form OEIS A016121 defined as the number of tuples $(a_1=1, a_2, ..., a_k)$ satisfying $a_i \leq a_{i+1} \leq 2a_i$ for each $i=1,2,\dots,k-1$.

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.

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 three terms are \begin{split} 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}

ADDED. In the case of equal arguments, the values $\big(f_k(t,t,\dots,t)\big)_{k\geq 1}$ apparently represent the row sums of the $t$-th power of the matrix $T$ defined in OEIS A097712 and also the $t$-th column of table in OEIS A125860.

In particular, $\big(f_k(1,1,\dots,1)\big)_{k\geq 1}$ form OEIS A016121 defined as the number of tuples $(a_1=1, a_2, ..., a_k)$ satisfying $a_i \leq a_{i+1} \leq 2a_i$ for each $i=1,2,\dots,k-1$.

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}

ADDED. In the case of equal arguments, the values $\big(f_k(t,t,\dots,t)\big)_{k\geq 0}$ apparently represent the row sums of the $t$-th power of the matrix $T$ defined in OEIS A097712 and also the $t$-th column of table in OEIS A125860.

In particular, $\big(f_k(1,1,\dots,1)\big)_{k\geq 0}$ form OEIS A016121 defined as the number of tuples $(a_1=1, a_2, ..., a_k)$ satisfying $a_i \leq a_{i+1} \leq 2a_i$ for each $i=1,2,\dots,k-1$.

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 three terms are \begin{split} 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}

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 three terms are \begin{split} 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}

ADDED. In the case of equal arguments, the values $\big(f_k(t,t,\dots,t)\big)_{k\geq 1}$ apparently represent the row sums of the $t$-th power of the matrix $T$ defined in OEIS A097712 and also the $t$-th column of table in OEIS A125860.

In particular, $\big(f_k(1,1,\dots,1)\big)_{k\geq 1}$ form OEIS A016121 defined as the number of tuples $(a_1=1, a_2, ..., a_k)$ satisfying $a_i \leq a_{i+1} \leq 2a_i$ for each $i=1,2,\dots,k-1$.