In the paper, A polytope related to empirical distributions, plane trees, parking functions, and the associahedron, Pitman and Stanley studied the $n$-dimensional polytope $$\Pi_n(\mathbf x)=\{y\in\Bbb{R}^n: y_i\geq0, y_1+\cdots+y_i\leq x_1+\cdots+x_i, \text{for all $1\leq i\leq n$}\}.$$ They noted the results \begin{align*} \text{Vol}(\Pi_n(\mathbf x)) &=\frac1{n!}\sum_{\mathbf{k}\in \mathbf{K}_n}\binom{n}{k_1,\dots,k_n}\,\,x_1^{k_1}\cdots x_n^{k_n} \\ &=\det\left(\frac{\chi(j-i+1\geq0)}{(j-i+1)!}\left(\sum_{h=1}^ix_h\right)^{j-i+1}\right)_{i,j=1}^n \end{align*} where $\chi$ is the indicator function and $$\mathbf{K}_n=\{\mathbf{k}\in\mathbb{Z}^n: k_i\geq0, k_1+\cdots+ k_n=n, k_1+\cdots k_i\leq i, \text{for all $1\leq i\leq n$}\}.$$ The set $\mathbf{K}_n$ has cardinality $\vert\mathbf{K}_n\vert=\frac1{n+1}\binom{2n}n$. Consider instead the determinant $$\det\left(\frac{\chi(j-i+1\geq0)}{(j-i+1)!}\cdot x_i^{j-i+1}\right)_{i,j=1}^n.$$ A composition of $n$ is a finite sequence of positive integers summing to $n$. To help us calculate the latter determinant, we introduce the set of compositions of length-$n$ $$\mathcal{B}_n=\{y\in\mathbb{Z}^n: y_i\geq0, \text{$y$ is a composition of $n$ with $0$ suffixes padded if necessary}\}.$$ For example, $\mathcal{B}_2=\{20, 11\}$ and $\mathcal{B}_3=\{300, {\color{red}{210}}, 120, 111\}$. Note $\vert\mathbf{B}_n\vert=2^{n-1}$.

QUESTION. Is this true? $$\det\left(\frac{\chi(j-i+1\geq0)}{(j-i+1)!}\cdot x_i^{j-i+1}\right)_{i,j=1}^n =\frac1{n!} \sum_{\mathbf{k}\in \mathcal{B}_n}(-1)^{\#(\mathbf{k})}\binom{n}{k_1,\dots,k_n} \,\,x_1^{k_1}\cdots x_n^{k_n},$$ where $\#(\mathbf{k})$ stands for the number of zeroes in $\mathbf{k}$.

REMARK. One may find it convenient to work with the alternative formulation $$\det\left(\frac{\chi(j-i+1\geq0)}{(j-i+1)!}\cdot x_i^{j-i+1}\right)_{i,j=1}^n =\prod_{k=1}^n\frac{k!}{(1+k)!}\cdot \det\left(\binom{1+j}{i}\cdot x_i^{j-i+1}\right)_{i,j=1}^n.$$ ${\color{blue}{POSTSCRIPT}}$. Max Alekseyev's comment requires some adjustment in the set $\mathcal{B}_n$. So, here is (I hope) the correct construction: $\mathbf{y}=(y_1,\dots,y_n)\in\mathcal{B}_n$ iff $y_1>0$; $y_i\in\mathbb{Z}_{\geq0}$ for all $i$; when $\mathbf{y}$ is read (cyclically) $y_1\rightarrow y_2\rightarrow\cdots\rightarrow y_n\rightarrow y_1$, each $y_i\neq0$ is followed by $y_i-1$ zeroes. Clearly, $y_i\leq n$ for all $i$.

For example, $\mathcal{B}_2=\{20, 11\}$ and $\mathcal{B}_3=\{300, {\color{red}{201}}, 120, 111\}$ and $\mathbf{B}_4=\{4000,3001,2020,2011,1300,1201,1120,1111\}$. Observe that $\vert \mathcal{B}_n\vert=2^{n-1}$, still.

  • 1
    $\begingroup$ Corrected formula: $$\frac1{n!}\sum_{\mathbf{k}\in \mathcal{B}_n}(-1)^{\#(\mathbf{k})}\binom{n}{k_1,\dots,k_n} \,\,x_1^{k_1}\cdots x_n^{k_n} = \sum_{i=0}^n \frac{(-1)^{n-i}}{(n-i)!} \iiint (x_1+\dots+x_i)^{n-i}\, dx_1\cdots dx_i.$$ $\endgroup$ Commented Apr 16, 2023 at 18:03
  • $\begingroup$ The equality in original Question does not hold already for $n=3$, when the left-hand side equals $$\frac{1}{6} x_{1}^{3} - \frac{1}{2} x_{1} x_{2}^{2} - \frac{1}{2} x_{1}^{2} x_{3} + x_{1} x_{2} x_{3},$$ while the right-hand side equals $$\frac{1}{6} x_{1}^{3} - \frac{1}{2} x_{1}^{2} x_{2} - \frac{1}{2} x_{1} x_{2}^{2} + x_{1} x_{2} x_{3}.$$ $\endgroup$ Commented Apr 17, 2023 at 1:15

1 Answer 1


Given the corrected definition of $\mathcal{B}_n$ in the Postscriptum, the equality does hold and can be proved by induction on $n$.

For $n=1$, the equality is trivial. For $n>1$, let's expand the determinant in the left-hand size of the equality over the first column to get $$\det\left(\frac{\chi(j-i+1\geq0)}{(j-i+1)!}\cdot x_i^{j-i+1}\right)_{i,j=1}^n = x_1 \det\left(\frac{\chi(j-i+1\geq0)}{(j-i+1)!}\cdot x_i^{j-i+1}\right)_{i,j=2}^n - \int_0^{x_1} dx_2 \det\left(\frac{\chi(j-i+1\geq0)}{(j-i+1)!}\cdot x_i^{j-i+1}\right)_{i,j=2}^n.$$

By the induction, the right-hand side in the expansion equals $$\frac1{n!} \sum_{\mathbf{k}\in \mathcal{B}_{n-1}}(-1)^{\#(\mathbf{k})}\binom{n}{1,k_1,\dots,k_{n-1}} \,\,x_1 x_2^{k_1}\cdots x_n^{k_{n-1}} - \frac1{n!} \sum_{\mathbf{k}\in \mathcal{B}_{n-1}}(-1)^{\#(\mathbf{k})}\binom{n}{k_1+1,k_2,\dots,k_{n-1}} \,\,x_1^{k_1+1}x_3^{k_2}\cdots x_n^{k_{n-1}}$$ $$=\frac1{n!} \sum_{\mathbf{t}\in \mathcal{B}_n}(-1)^{\#(\mathbf{t})}\binom{n}{t_1,\dots,t_n} \,\,x_1^{t_1} x_2^{t_2}\cdots x_n^{t_n},$$ where the two sums in the left-hand side correspond to the following two cases in the right-hand size:

  • $t_1=1$ and $t_{i+1} = k_i$ for $i=1,2,\dots,n-1$; and
  • $t_1=k_1+1>1$, $t_2=0$, and $t_{i+1} = k_i$ for $i=2,\dots,n-1$.


  • $\begingroup$ This is good, thanks Max. $\endgroup$ Commented Apr 17, 2023 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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