Talk:Inversion (discrete mathematics)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science  
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 
WikiProject Mathematics (Rated Stub-class, Low-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Stub Class
Low Importance
 Field: Discrete mathematics

Bring over some content?[edit]

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[edit]

Copied from talk page:
Hi Lipedia,
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. Lipedia (talk) 14:57, 9 July 2012 (UTC)

Contradictions[edit]

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)