# Catalan sequences vs composition sequences

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.

• 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.$$ Commented Apr 16, 2023 at 18:03
• 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}.$$ Commented Apr 17, 2023 at 1:15

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