1

Let $I_n:=\{1, \ldots, n\}$ where $n\in\mathbb N$. I'm wondering whether is there a way to write $\displaystyle\prod_{i<j} (j-i)$ as a sum?

The product above is taken over all pairs $(i, j)\in I_n\times I_n$ such that $i<j$.

Thanks.

Context: I want to show $$\prod_{i<j} (\sigma_j-\sigma_i)=(-1)^{\imath(\sigma)}\prod_{i<j} (j-i),$$ where $\sigma$ is a permutation of $I_n$, $\sigma_j:=\sigma(j)$ and $$\imath(\sigma):=\#\{(i, j)\in I_n\times I_n; i<j\quad \textrm{and}\ \sigma(i)>\sigma(j)\},$$ that is $\imath(\sigma)$ is the number of iversions $\sigma$ performs.

PtF
  • 9,655
  • This likely doesn't help, but what you have here is the square root of the discriminant of Wilkinson's polynomial for various values of $n$. It is also the determinant of a special Vandermonde matrix. – Michael Burr Mar 01 '15 at 20:27
  • The determinant might work for I may write it as a sum indexed on permutations, which matrix is that? – PtF Mar 01 '15 at 20:31
  • The Vandermonde matrix has this product as its determinant. You'll want to substitute $1,\dots,n$ as the $x_i$'s in the matrix. – Michael Burr Mar 01 '15 at 20:32
  • Intersting, that will help, thanks =) – PtF Mar 01 '15 at 20:33
  • @Michael Burr: The Van der Monde route seems to give a sum of sorts, though it looks as hard as the original product. Isn't it something like $\pm \sum_{ \sigma \in S_{n}} ({\rm sign} \sigma ) \prod_{j=1}^{n} j^{\sigma(j)-1}$? – Geoff Robinson Mar 01 '15 at 20:34
  • Indeed it does not make the expression simpler but it helps for I'm working with permutations and the sum you gave me uses permutations explicitely..Indeed I want to compare the product above with $\prod_{i<j} (\sigma_j-\sigma_i)$ where $\sigma$ is a permutation of the first $n$ integers. I want to show they differ by a sign.. – PtF Mar 01 '15 at 20:37
  • @GeoffRobinson That sum looks about right. The natural sums that you get out of this product are ugly, so I think that some combinatorial description (or some other fancy computation) would provide the best description. – Michael Burr Mar 01 '15 at 20:38
  • 1
    @PtF Have you noticed that your product is equal to $\displaystyle\prod_{j=1}^{n}(j-1)!$ thus it is linked to Barnes G-function:http://en.wikipedia.org/wiki/Barnes_G-function See also OEIS: https://oeis.org/search?q=1%2C+1%2C+2%2C+12%2C+288%2C+34560%2C+24883200&language=english&go=Search – Olivier Oloa Mar 01 '15 at 20:48

1 Answers1

1

It can be proven by mathematical induction that for a set $I_n:=\{1, \ldots, n\}$, the set of distances between pairs of its elements is $D_n:=\{n, n-1, \ldots, 2, 1\}$, where the first element represents the number of pairs with distance $1$, and the last element is the number of pairs with distance $n$. This is equivalent to $D_n=n-I_n+1$. Your product is asking for the $D_n(k)$ multiples of $k$, or, in other words, $$\displaystyle\prod_{k=1}^{n} (n-k+1)k=n(n-1)!\cdot n!=(n!)^2$$ While not a sum, I think this result is pretty important.

BHT
  • 2,215
  • Your formula is wrong. For example, for $n=2,3,4$ the correct values are $1,2,12$ rather than what your formula suggests. The correct formula can be found in Olivier Oloa's comment. – Yuval Filmus Mar 01 '15 at 22:47