10
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ The equal arguments case looks like it should also give the Ehrhart polynomial of some lattice polytope. $\endgroup$ May 9 at 2:20
  • 3
    $\begingroup$ FWIW it seems that $f_k(1,2,3,\ldots,k-2,k-2,k)=a(k+1)$, where $a(k)$ is A107877. $\endgroup$
    – BillyJoe
    May 10 at 17:32
  • 1
    $\begingroup$ @BillyJoe: Nice catch! In fact, it is stated there as conjecture by Benedict W. J. Irwin. $\endgroup$ May 10 at 17:49
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – BillyJoe
    May 10 at 21:08
  • 1
    $\begingroup$ 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. $\endgroup$ May 11 at 7:19

2 Answers 2

11
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.