Sum of Vandermonde determinant

Question

Given positive integers $n$ and $d$, where $d\geq 2$, I would like to compute the sum $$\displaystyle\sum_{0\leq i_{1} < i_{2} < ... < i_{d}\leq n} \quad\displaystyle\prod_{1 \leq p < q \leq d}\left(i_{q} - i_{p}\right).$$ Since there are $d\choose 2$ factors in the product, the sum should return a polynomial in $n$ of degree $d(d+1)/2$. Ideally I would like to know all coefficients of the polynomial in $n$. The leading coefficient (i.e., coefficient of $n^{d(d+1)/2}$) is of particular interest.

For example, when $d=2$, our sum becomes $\displaystyle\sum_{i=0}^{n}\displaystyle\sum_{j=i+1}^{n}(j-i) = \frac{1}{6}n(n+1)(n+2)$, and the leading coefficient (of $n^3$) is $1/6$.

When $d=3$, our sum gives $\displaystyle\sum_{i=0}^{n}\displaystyle\sum_{j=i+1}^{n}\displaystyle\sum_{k=j+1}^{n}(k-j)(j-i)(k-i) = \frac{1}{180}(n-1)n(n+1)^{2}(n+2)(n+3)$, and the leading coefficient (of $n^{6}$) is $1/180$.

For $d=4$, WolframAlpha gives $$\displaystyle\sum_{i=0}^{n}\displaystyle\sum_{j=i+1}^{n}\displaystyle\sum_{k=j+1}^{n}\displaystyle\sum_{l=k+1}^{n}(l-k)(l-j)(l-i)(k-j)(k-i)(j-i)\\ = \frac{1}{25200}(n-2)(n-1)n^{2}(n+1)^{2}(n+2)^{2}(n+3)(n+4)$$ and the leading coefficient (of $n^{10}$) is $1/25200$.

I am not sure if this object is well-known, or has a name. Any references will be great too.

Answer 1

In terms of the leading term coefficient the following identities hold true: \begin{eqnarray} c_d&=&\int\limits_{0 \le x_1 \le \cdots x_d \le 1} \prod\limits_{1 \le p < q \le d} (x_p - x_q)\cdot \prod\limits_{p=1}^d dx_p\\ &=&\sum\limits_{\sigma \in \Pi} \mbox{sign($\sigma$)} \frac{1}{\prod\limits_{i=1}^d \sum\limits_{j=1}^i \sigma_j} \quad (1)\\ &=& \int\limits_{[0,1]^d} \left(\prod\limits_{p=1}^d x_p^{\binom{p}{2}+p-1} \right) \cdot \prod\limits_{p=1}^d \prod\limits_{q=p+1}^d \left(1-\prod\limits_{\xi=p}^{q-1} x_\xi\right) \cdot \prod\limits_{p=1}^d d x_p \quad (2) \\ &\underbrace{=}_{?}& \prod\limits_{\xi=1}^{d-1} \frac{(\xi!)^2}{(2 \xi+1)!} \end{eqnarray} where in $(1)$ we expanded the Vandermonde determinant in a sum over permutations $\Pi$ and then integrated term by term and in $(2)$ we we used the trick $1/p = \int\limits_0^1 x^{p-1} dx$ and the definition of the Vandermonde determinant again. The representations above are readily used to compute the result for $d \le 9$. We have:

In[484]:= d =.;
ss = Table[
  Total[Signature[#] Product[1/(Total[Take[#, i]]), {i, 1, d}] & /@ 
    Permutations[Range[1, d]]], {d, 1, 9}]
Table[Expand[
   Product[x[p]^(Binomial[p, 2] + p - 1), {p, 1, 
      d}] Product[(1 - Product[x[xi], {xi, p, q - 1}]), {p, 1, d}, {q,
       p + 1, d}]] /. x[n_]^p_. :> 1/(p + 1), {d, 1, 9}]
Table[Product[(xi!)^2/(2 xi + 1)!, {xi, 1, d - 1}], {d, 1, 9}]

Update: Let us denote: \begin{eqnarray} {\mathcal S}_d^{(n)} := \sum\limits_{0 \le i_1 < i_2 < \cdots < i_d \le n} \prod\limits_{1 \le p < q \le d} (i_q-i_p) \end{eqnarray} for $n \ge d-1$. Then my conjecture is the following: \begin{eqnarray} {\mathcal S}_d^{(n)} = \left[\prod\limits_{\xi=1}^{d-1} \frac{(\xi!)^2}{(2 \xi+1)!}\right] \cdot \left[\prod\limits_{j=-d+1}^1 (n+j)^{\lceil \frac{j+d-1}{2} \rceil}\right] \cdot (n+2)^{\lfloor \frac{d}{2}\rfloor} \cdot \left[\prod\limits_{j=3}^d (n+j)^{\lceil \frac{d-j+1}{2} \rceil }\right] \end{eqnarray}

I have verified this conjecture for $d \le 6$ using the code below:

d = 2; Clear[a]; Clear[aa]; i[0] = 0;
aa = Table[a[p], {p, 0, d - 1}];
smnD = Product[i[q] - i[p], {p, 1, d}, {q, p + 1, d}];
subst = First@
    Solve[CoefficientList[
       smnD - (Sum[Binomial[i[d] - i[d - 1], p] a[p], {p, 0, d - 1}]),
        i[d]] == 0, aa] // Simplify;
(*Sum over i[d] done.*)
S = Sum[Binomial[n + 1 - i[d - 1], p + 1] a[p], {p, 0, d - 1}] /. 
   subst;
upLim = d - 1;
For[count = 1, count <= d - 1, count++,
  upLim = upLim + d - count;
  aa = Table[a[p], {p, 0, upLim}];
  subst = 
   First@Solve[
      CoefficientList[
        FunctionExpand@(S - (Sum[
             Binomial[i[d - count] - i[d - count - 1], p] a[p], {p, 0,
               upLim}])), i[d - count]] == 0, aa] // Simplify;
  (*Sum over i[d-count] done.*)
  S = Sum[
     Binomial[n + 1 - i[d - count - 1], p + 1] a[p], {p, 0, 
      upLim}] /. subst;
  Print["count=", count, "done"];
  ];
Factor[FunctionExpand@S]

Answer 2

This is a follow up on Przemo's answer in deriving the final expression of the leading coefficient $c_{d}$. Notice that $d! c_{d}$ equals the Vandermonde determinant integrated over $[0,1]^{d}$. In an 1955 paper by De Bruijn (see toward the end of Sec. 9), it is proved that

$$\int_{[0,1]^{d}}\prod_{1\leq i < j \leq d} |x_{i} - x_{j}| \: {\rm{d}}x_{1} ... {\rm{d}}x_{d} = \frac{\{1! \times 2! \times 3! \times ... \times (d-1)!\}^{2} d!}{1!\times 3! \times 5! \times ... \times (2d-1)!}.$$

That proof utilizes the result (also derived in that paper) that integrals of this type are equal to certain Pfaffian form. Equating the above with $d! c_{d}$ recovers the expression conjectured by Przemo:

$$c_{d} = \prod\limits_{\xi=1}^{d-1} \frac{(\xi!)^2}{(2 \xi+1)!}.$$