Talk:Inversion (discrete mathematics)

Bring over some content?

The discussion at Permutation#Inversions has a fair amount of content that would be worth bringing over to this article. I may do some of it myself (and perhaps do further editing of what's already here), but I'd love some help :) --Joel B. Lewis (talk) 22:07, 29 July 2011 (UTC)

Contradictions

In the articles Inversion (discrete mathematics), Permutation, Lehmer code and Factorial number system, the terms "inversion vector", "inversion table" and "Lehmer code" refer to similar concepts, but are used quite inconsistently. Sometimes the inversion vector is the Lehmer code of the inverse permutation and sometimes they are identical, sometimes the most significant digit corresponds to the first entry of the vector and sometimes to the last, sometimes the leading (or trailing) zero is omitted, sometimes not and so on. I am aware that different definitions are used in the literature, see Talk:Lehmer code#Ambiguity about the term and its meaning, but the current state is very confusing and frustrating for the reader. In my experience, the usually employed definitions are:

The inversion vector is the same as inversion table; the j-th entry of the vector is the number of elements in the one-line-notation to the left of j which are larger than j (see TAOCP Vol. 3 or MathWorld):

$b_{j}=\#\left\{i\in \{1,\ldots ,n\}\mid i>j~{\text{and}}~\sigma ^{-1}(i)<\sigma ^{-1}(j)\right\}$

The Lehmer code is the inversion vector of the inverse permutation; the i-th entry of the vector is the number of elements in the one-line-notation to the right of σ(i) which are smaller than σ(i) (see Talk:Lehmer code for references):

$l_{i}=\#\left\{j\in \{1,\ldots ,n\}\mid i<j~{\text{and}}~\sigma (i)>\sigma (j)\right\}$

For example, the inversion vector of the permutation σ=(3,5,1,2,4) is b=(2,2,0,1,0) and its Lehmer code is l=(2,3,0,0,0). In the corresponding Rothe diagram, the inversion vector is the sum of crosses in each column, read from left to right, and the Lehmer code is the sum of crosses in each row, read from top to bottom. To convert these vectors into factorial numbers, the first entry is taken as the most significant digit and the last entry as the least significant digit (which is always zero). It would be great, if the articles would reflect these concepts in a consistent manner. This especially applies to the illustrations, which all employ uncommon conventions, in my opinion. Best wishes, --Quartl (talk) 19:19, 6 March 2013 (UTC)

One of the two Rothe diagram graphics I suggest for the article

Hello @Quartl:, @Uncle G:, @Joel B. Lewis:, @David Eppstein:, and everyone else who is interested in this article.

TL;DR: I wrote v:Inversion (discrete mathematics). Feel free to take a look at it, and concider if this article should use the same terminology and formulas.

As Quartl has pointed out, this article is quite confusing at the moment. To me this is mainly because the inversion vector and the reflected factorial number are conflated. The history is as follows:

In December 2010 Uncle G added the definition of the inversion vector with Pemmaraju & Skiena as a source:

https://en.wikipedia.org/w/index.php?title=Inversion_(discrete_mathematics)&diff=prev&oldid=400850635

The inversion vector $V[2..n]$ of the sequence is defined for $i=2..n$ as $V[i]=\left\vert \{A[1..i-1]|A[k]>A[i]\}\right\vert$.

The formula looks weird to me, and I find the description opaque. But the definition at P&S is straightforward: "The i-th element of V is the number of elements in π greater than i to the left of i." That's the column sums of the Rothe diagram, which almost everyone seems to call the inversion vector.

In July 2011 Joel B. Lewis replaced the formula by a much nicer one, but unfortunately it does not match the definition of V in P&S anymore.

https://en.wikipedia.org/w/index.php?title=Inversion_(discrete_mathematics)&diff=next&oldid=421057003

The inversion vector V(i) of the sequence is defined for i = 2, ..., n as $V[i]=\left\vert \{k\mid k<i{\text{ and }}A(k)>A(i)\}\right\vert$.

This new formula defines the reflected factorial number. This is how the reflected factorial number came into my files under the name "inversion vector" - also visible in the file that currently illustrates this article. I don't know if there are sources that actually call the reflected factorial number "inversion vector", but P&S does not.

Whichever words we use, there are three essentially different vectors (not counting reflections and omitting 0s) that this article should define. I have explained them in painstaking detail at v:Inversion (discrete mathematics) under names that should be uncontroversial. I suggest that the first section from there becomes the new basis of the Definitions section in this article. I would also include one or both of the Rothe diagram graphics. Watchduck (quack) 23:41, 4 November 2016 (UTC)