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)

Images

Copied from user talk page:
Hi Lipedia [Watchduck],
First, I wanted to say that it's nice to see that someone is doing some serious work adding illustrations to articles in discrete math and combinatorics. (Maybe also you do this in other areas, but those are the areas in which I watch pages.) Unfortunately, I think some of your pictures go overboard in how much information they contain. As a particular example, the four figures in Inversion (discrete mathematics) seem to take up as much space as the entire text of the article (though partly because this article is woefully under cared for); two of the four contain so much information that it requires several minutes of study to decipher them, and in both of these there seems to be notations/highlighting/colors that aren't explained at all. If you're interested, I'd be happy to discuss this with you in more detail -- let me know! (Perhaps we can also work on expanding and improving the text of the article so the images aren't quite so overwhelming.) --JBL (talk) 19:23, 8 July 2012 (UTC)

Since I included File:Inversion set and vector of a permutation.svg at the beginning, the example section at the end may be too much. I should move it to v:Inversion (discrete mathematics). I am going to create a link to this new page anyway. Watchduck (talk) 14:57, 9 July 2012 (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 r.f.n.. I don't know if there are sources that actually call the r.f.n. "inversion vector", but P&S does not. I don't recall where the use of "inversion vector" for the r.f.n. came from, but I started using it like that in 2010 (and that's how it's still seen in the current illustration of the article).

The article Permutation still invites to confuse the r.f.n. with the Lehmer code: "express N in the factorial number system [... then interpret] this sequence as a Lehmer code or (almost equivalently) as an inversion table"

A similar conflation of concepts and terms is found in the Fxtbook by Jörg Arndt: "The factorial representation computed is called the Lehmer code of the permutation. [...] An alternative term for the Lehmer code is inversion table"

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)