Catalan Sequences vs Composition Sequences – Differences and Applications

co.combinatoricsconvex-polytopesenumerative-combinatorics

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.

Best Answer

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

QED

Related Question