2252:
1064:
1091:} is sought). Alternatively the entries of the Lehmer code can be processed from left to right, and interpreted as a number determining the next choice of an element as indicated above; this requires maintaining a list of available elements, from which each chosen element is removed. In the example this would mean choosing element 1 from {A,B,C,D,E,F,G} (which is B) then element 4 from {A,C,D,E,F,G} (which is F), then element 0 from {A,C,D,E,G} (giving A) and so on, reconstructing the sequence B,F,A,G,D,E,C.
775:
1059:{\displaystyle {\begin{matrix}\mathbf {1} &5&0&6&3&4&2\\1&\mathbf {4} &0&5&2&3&1\\1&4&\mathbf {0} &4&2&3&1\\1&4&0&\mathbf {3} &1&2&0\\1&4&0&3&\mathbf {1} &2&0\\1&4&0&3&1&\mathbf {1} &0\\1&4&0&3&1&1&\mathbf {0} \\\end{matrix}}}
2228:
to a friend of his at a time when he was trying to make up his mind and choose one out eleven prospective brides as his second wife. His first marriage had been an unhappy one, having been arranged without himself being consulted, and he was thus very concerned that he could reach the right decision.
748:
This number to encode each object can be found by direct counting, in several ways (directly counting inversions, or correcting the total number of objects smaller than a given one, which is its sequence number starting from 0 in the set, by those that are unavailable at its position). Another method
686:
different ways (because there are now 2 forbidden values), and so forth. Translating this freedom of choice at each step into a number, one obtains an encoding algorithm, one that finds the Lehmer code of a given permutation. One need not suppose the objects permuted to be numbers, but one needs a
2216:
The interviewer thus knows the rank of the k applicant, therefore, at the moment of making his k decision, the interviewer knows only the k first elements of the Lehmer code whereas he would need to know all of them to make a well informed decision. To determine the optimal strategies (i.e. the
2204:
This is an optimal stop problem, a classic in decision theory, statistics and applied probabilities, where a random permutation is gradually revealed through the first elements of its Lehmer code, and where the goal is to stop exactly at the element k such as σ(k)=n, whereas the only available
1538:
347:
1735:
1944:
2208:
In less mathematical words : a series of n applicants are interviewed one after the other. The interviewer must hire the best applicant, but must make his decision (“Hire” or “Not hire”) on the spot, without interviewing the next applicant (and
635:, or by counting non-inversions rather than inversions; while this does not produce a fundamentally different type of encoding, some properties of the encoding will change correspondingly. In particular counting inversions with a fixed smaller value
2178:
1396:
191:
768:
is no longer available). Concretely a Lehmer code for the permutation B,F,A,G,D,E,C of letters, ordered alphabetically, would first give the list of sequence numbers 1,5,0,6,3,4,2, which is successively transformed
1571:
129:
1188:
1385:
2059:
1795:
530:, which is also the number of adjacent transpositions that are needed to transform the permutation into the identity permutation. Other properties of the Lehmer code include that the
1789:
1242:
1991:
166:
numbers, but not all such sequences are valid since every number must be used only once. By contrast the encodings considered here choose the first number from a set of
1069:
where the final line is the Lehmer code (at each line one subtracts 1 from the larger entries to the right of the boldface element to form the next line).
2075:
1533:{\displaystyle \{\omega \in B(k)\}\Leftrightarrow \{L(k,\omega )=0\}\quad {\text{and}}\quad \{\omega \in H(k)\}\Leftrightarrow \{L(k,\omega )=k-1\}.}
342:{\displaystyle L(\sigma )=(L(\sigma )_{1},\ldots ,L(\sigma )_{n})\quad {\text{where}}\quad L(\sigma )_{i}=\#\{j>i:\sigma _{j}<\sigma _{i}\},}
1730:{\displaystyle N_{b}(\omega )=\sum _{1\leq k\leq n}\ 1\!\!1_{B(k)}\quad {\text{and}}\quad N_{b}(\omega )=\sum _{1\leq k\leq n}\ 1\!\!1_{H(k)}.}
2242:
2364:
69:
177:
values, and so forth decreasing the number of possibilities until the last number for which only a single fixed value is allowed;
1076:, in order from right to left, correct the items to its right by adding 1 to all those (currently) greater than or equal to
1119:
1354:
2187:
1276:
760:, in order from left to right, correct the items to its right by subtracting 1 from all entries (still) greater than
2408:
1072:
For decoding a Lehmer code into a permutation of a given set, the latter procedure may be reversed: for each entry
45:
1998:
1939:{\displaystyle \mathbb {P} (B(k))=\mathbb {P} (L(k)=0)=\mathbb {P} (H(k))=\mathbb {P} (L(k)=k-1)={\tfrac {1}{k}}.}
1245:
691:
of the set of objects. Since the code numbers are to start from 0, the appropriate number to encode each object
2183:
2217:
strategy maximizing the probability of a win), the statistical properties of the Lehmer code are crucial.
1746:
1197:
1563:
700:
by is the number of objects that were available at that point (so they do not occur before position
1955:
756:} obtained by representing each object by its mentioned sequence number, and then for each entry
749:
which is in-place, but not really more efficient, is to start with the permutation of {0, 1, ...
591:
41:
2398:
550:), that any value 0 in the code represents a right-to-left minimum in the permutation (i.e., a
2372:
2186:
notation), which allows us to recover the product formula for the generating function of the
1087:} as sequence numbers (which amounts to adding 1 to each entry if a permutation of {1, 2, ...
2403:
531:
185:
can be defined, the Lehmer code has several additional useful properties; it is the sequence
52:
8:
1949:
679:
different ways (because choosing the same number as the first is forbidden), the next in
2342:
2320:
2257:
2205:
information (the k first values of the Lehmer code) is not sufficient to compute σ(k).
181:
sequence of numbers chosen from these sets encodes a single permutation. While several
2237:
Two similar vectors are in use. One of them is often called inversion vector, e.g. by
2298:
2251:
2225:
2199:
1280:
2332:
2221:
2173:{\displaystyle G(s)=\prod _{k=1}^{n}G_{k}(s)\ =\ {\frac {s^{\overline {n}}}{n!}}}
1272:
1105:
688:
2392:
2238:
534:
of the encodings of two permutations is the same as that of their sequences (
21:
2337:
586:
similarly signifies a right-to-left maximum, and that the Lehmer code of
33:
17:
2346:
1343:) be the event "there is right-to-left minimum (resp. maximum) at rank
713:
actually chosen. (Inevitably such objects must appear at some position
650:, which can be seen to be the Lehmer code of the inverse permutation.
2278:
Lehmer, D.H. (1960), "Teaching combinatorial tricks to a computer",
601:
Variations of this encoding can be obtained by counting inversions (
598:
in lexicographical order (numbering the positions starting from 0).
182:
29:
2280:
Proc. Sympos. Appl. Math. Combinatorial
Analysis, Amer. Math. Soc.
1094:
2243:
Inversion (discrete mathematics) § Inversion related vectors
2365:"A permutation representation that knows what "Eulerian" means"
1558:) of right-to-left minimum (resp. maximum) for the permutation
731:) will be an inversion, which shows that this number is indeed
1387:
which exhibit a right-to-left minimum (resp. maximum) at rank
1321:
is strictly smaller (resp. strictly bigger) than each element
594:
representation of its position in the list of permutations of
124:{\displaystyle n!=n\times (n-1)\times \cdots \times 2\times 1}
2299:"Sur la numération factorielle, application aux permutations"
666:
objects is to observe that the first object can be chosen in
1286:
1080:; finally interpret the resulting permutation of {0, 1, ...
1279:, because they are projections on different factors of a
2384:, vol. 3, Reading: Addison-Wesley, pp. 12–13
1922:
1750:
1358:
780:
764:(to reflect the fact that the object corresponding to
2369:
2078:
2001:
1958:
1798:
1749:
1574:
1399:
1357:
1200:
1122:
778:
194:
72:
63:
The Lehmer code makes use of the fact that there are
2362:
2247:
2323:(1989), "Who solved the secretary problem ?",
1183:{\displaystyle \times \times \cdots \times \times }
55:, but the code had been known since 1888 at least.
2172:
2053:
1985:
1938:
1783:
1729:
1532:
1380:{\displaystyle \scriptstyle \ {\mathfrak {S}}_{n}}
1379:
1236:
1182:
1058:
341:
123:
1963:
1962:
1773:
1757:
1704:
1703:
1626:
1625:
1099:
391:that are smaller than it, a number between 0 and
2390:
2363:Mantaci, Roberto; Rakotondrajao, Fanja (2001),
1566:each with a respective parameter of 1/k :
1095:Applications to combinatorics and probabilities
617:, by counting inversions with a fixed smaller
2303:Bulletin de la Société Mathématique de France
1275:on , and these random variables are mutually
1104:The Lehmer code defines a bijection from the
2054:{\displaystyle G_{k}(s)={\frac {k-1+s}{k}},}
1524:
1491:
1485:
1464:
1454:
1427:
1421:
1400:
1231:
1201:
333:
295:
170:values, the next number from a fixed set of
40:numbers. It is an instance of a scheme for
2336:
1884:
1858:
1826:
1800:
1287:Number of right-to-left minima and maxima
704:), but which are smaller than the object
51:The Lehmer code is named in reference to
2319:
2193:
653:
2313:
2296:
1562:can be written as a sum of independent
2391:
2290:
2277:
2213:without interviewing all applicants).
2063:therefore the generating function of
658:The usual way to prove that there are
162:, then it is encoded by a sequence of
2379:
2271:
526:is the total number of inversions of
2232:
1784:{\displaystyle \scriptstyle \ \!],}
1365:
1237:{\displaystyle \{0,1,\ldots ,k-1\}}
672:different ways, the next object in
13:
2188:Stirling numbers of the first kind
1952:for the Bernoulli random variable
292:
14:
2420:
470:counts the number of inversions (
2250:
1291:Definition : In a sequence
1271:defines a uniformly distributed
1048:
1004:
960:
916:
872:
828:
784:
2382:The art of computer programming
2356:
1652:
1646:
1463:
1457:
1351:is the set of the permutations
366:counts the number of terms in (
269:
263:
2297:Laisant, Charles-Ange (1888),
2131:
2125:
2088:
2082:
2018:
2012:
1978:
1972:
1915:
1900:
1894:
1888:
1877:
1874:
1868:
1862:
1851:
1842:
1836:
1830:
1819:
1816:
1810:
1804:
1774:
1770:
1758:
1754:
1719:
1713:
1669:
1663:
1641:
1635:
1591:
1585:
1509:
1497:
1488:
1482:
1476:
1445:
1433:
1424:
1418:
1412:
1244:. As a consequence, under the
1177:
1171:
1165:
1159:
1147:
1135:
1129:
1123:
1100:Independence of relative ranks
280:
273:
260:
251:
244:
223:
216:
210:
204:
198:
142:is specified by the sequence (
134:permutations of a sequence of
100:
88:
1:
2264:
1986:{\displaystyle 1\!\!1_{B(k)}}
646:gives the inversion table of
2371:(4): 101–108, archived from
2154:
1743:follows the uniform law on
662:! different permutations of
7:
572:to its right), and a value
158:) of its images of 1, ...,
58:
10:
2425:
2197:
1564:Bernoulli random variables
631:rather than smaller index
452:is called an inversion of
138:numbers. If a permutation
1116:to the Cartesian product
1190:, where designates the
352:in other words the term
44:and is an example of an
2409:Resampling (statistics)
592:factorial number system
28:is a particular way to
2174:
2114:
2055:
1987:
1940:
1785:
1731:
1534:
1381:
1332:, i.e., to its right.
1238:
1184:
1060:
343:
125:
42:numbering permutations
2338:10.1214/ss/1177012493
2224:clearly exposed this
2194:The secretary problem
2175:
2094:
2056:
1988:
1941:
1786:
1732:
1535:
1382:
1304:right-to-left minimum
1239:
1185:
1061:
654:Encoding and decoding
532:lexicographical order
344:
126:
20:and in particular in
2076:
1999:
1956:
1796:
1747:
1572:
1397:
1355:
1246:uniform distribution
1198:
1120:
776:
192:
70:
53:Derrick Henry Lehmer
2380:Knuth, Don (1981),
2325:Statistical Science
2321:Ferguson, Thomas S.
1950:generating function
590:coincides with the
414:A pair of indices (
2258:Mathematics portal
2170:
2051:
1983:
1936:
1931:
1781:
1780:
1727:
1696:
1618:
1530:
1391:. We clearly have
1377:
1376:
1234:
1180:
1056:
1054:
613:rather than fixed
486:. It follows that
482:fixed and varying
411:different values.
382:) to the right of
339:
121:
2226:secretary problem
2200:Secretary problem
2168:
2157:
2142:
2136:
2046:
1930:
1753:
1699:
1675:
1650:
1621:
1597:
1461:
1361:
1281:Cartesian product
561:smaller than any
267:
36:of a sequence of
2416:
2385:
2376:
2350:
2349:
2340:
2317:
2311:
2310:
2294:
2288:
2287:
2275:
2260:
2255:
2254:
2233:Similar concepts
2184:rising factorial
2179:
2177:
2176:
2171:
2169:
2167:
2159:
2158:
2150:
2144:
2140:
2134:
2124:
2123:
2113:
2108:
2060:
2058:
2057:
2052:
2047:
2042:
2025:
2011:
2010:
1992:
1990:
1989:
1984:
1982:
1981:
1945:
1943:
1942:
1937:
1932:
1923:
1887:
1861:
1829:
1803:
1790:
1788:
1787:
1782:
1751:
1736:
1734:
1733:
1728:
1723:
1722:
1697:
1695:
1662:
1661:
1651:
1648:
1645:
1644:
1619:
1617:
1584:
1583:
1542:Thus the number
1539:
1537:
1536:
1531:
1462:
1459:
1386:
1384:
1383:
1378:
1375:
1374:
1369:
1368:
1359:
1257:, the component
1243:
1241:
1240:
1235:
1189:
1187:
1186:
1181:
1086:
1065:
1063:
1062:
1057:
1055:
1051:
1007:
963:
919:
875:
831:
787:
755:
722:
685:
678:
671:
645:
630:
581:
571:
560:
525:
451:
431:
410:
400:
348:
346:
345:
340:
332:
331:
319:
318:
288:
287:
268:
265:
259:
258:
231:
230:
176:
130:
128:
127:
122:
2424:
2423:
2419:
2418:
2417:
2415:
2414:
2413:
2389:
2388:
2359:
2354:
2353:
2318:
2314:
2295:
2291:
2276:
2272:
2267:
2256:
2249:
2235:
2222:Johannes Kepler
2202:
2196:
2180:
2160:
2149:
2145:
2143:
2119:
2115:
2109:
2098:
2077:
2074:
2073:
2068:
2061:
2026:
2024:
2006:
2002:
2000:
1997:
1996:
1968:
1964:
1957:
1954:
1953:
1946:
1921:
1883:
1857:
1825:
1799:
1797:
1794:
1793:
1748:
1745:
1744:
1737:
1709:
1705:
1679:
1657:
1653:
1647:
1631:
1627:
1601:
1579:
1575:
1573:
1570:
1569:
1555:
1547:
1540:
1458:
1398:
1395:
1394:
1370:
1364:
1363:
1362:
1356:
1353:
1352:
1326:
1319:
1300:
1296:
1289:
1273:random variable
1270:
1256:
1199:
1196:
1195:
1121:
1118:
1117:
1115:
1106:symmetric group
1102:
1097:
1081:
1053:
1052:
1047:
1045:
1040:
1035:
1030:
1025:
1020:
1014:
1013:
1008:
1003:
1001:
996:
991:
986:
981:
975:
974:
969:
964:
959:
957:
952:
947:
942:
936:
935:
930:
925:
920:
915:
913:
908:
903:
897:
896:
891:
886:
881:
876:
871:
869:
864:
858:
857:
852:
847:
842:
837:
832:
827:
825:
819:
818:
813:
808:
803:
798:
793:
788:
783:
779:
777:
774:
773:
750:
744:
714:
712:
699:
680:
673:
667:
656:
644:
636:
629:
621:
573:
570:
562:
559:
551:
549:
540:
524:
510:
498:
487:
469:
450:
441:
433:
423:
402:
401:, allowing for
392:
390:
381:
372:
365:
327:
323:
314:
310:
283:
279:
264:
254:
250:
226:
222:
193:
190:
189:
171:
157:
148:
71:
68:
67:
61:
12:
11:
5:
2422:
2412:
2411:
2406:
2401:
2387:
2386:
2377:
2358:
2355:
2352:
2351:
2331:(3): 282–289,
2312:
2289:
2269:
2268:
2266:
2263:
2262:
2261:
2234:
2231:
2198:Main article:
2195:
2192:
2166:
2163:
2156:
2153:
2148:
2139:
2133:
2130:
2127:
2122:
2118:
2112:
2107:
2104:
2101:
2097:
2093:
2090:
2087:
2084:
2081:
2072:
2066:
2050:
2045:
2041:
2038:
2035:
2032:
2029:
2023:
2020:
2017:
2014:
2009:
2005:
1995:
1980:
1977:
1974:
1971:
1967:
1961:
1935:
1929:
1926:
1920:
1917:
1914:
1911:
1908:
1905:
1902:
1899:
1896:
1893:
1890:
1886:
1882:
1879:
1876:
1873:
1870:
1867:
1864:
1860:
1856:
1853:
1850:
1847:
1844:
1841:
1838:
1835:
1832:
1828:
1824:
1821:
1818:
1815:
1812:
1809:
1806:
1802:
1792:
1779:
1776:
1772:
1769:
1766:
1763:
1760:
1756:
1726:
1721:
1718:
1715:
1712:
1708:
1702:
1694:
1691:
1688:
1685:
1682:
1678:
1674:
1671:
1668:
1665:
1660:
1656:
1643:
1640:
1637:
1634:
1630:
1624:
1616:
1613:
1610:
1607:
1604:
1600:
1596:
1593:
1590:
1587:
1582:
1578:
1568:
1553:
1545:
1529:
1526:
1523:
1520:
1517:
1514:
1511:
1508:
1505:
1502:
1499:
1496:
1493:
1490:
1487:
1484:
1481:
1478:
1475:
1472:
1469:
1466:
1456:
1453:
1450:
1447:
1444:
1441:
1438:
1435:
1432:
1429:
1426:
1423:
1420:
1417:
1414:
1411:
1408:
1405:
1402:
1393:
1373:
1367:
1324:
1317:
1298:
1294:
1288:
1285:
1266:
1252:
1233:
1230:
1227:
1224:
1221:
1218:
1215:
1212:
1209:
1206:
1203:
1179:
1176:
1173:
1170:
1167:
1164:
1161:
1158:
1155:
1152:
1149:
1146:
1143:
1140:
1137:
1134:
1131:
1128:
1125:
1111:
1101:
1098:
1096:
1093:
1067:
1066:
1050:
1046:
1044:
1041:
1039:
1036:
1034:
1031:
1029:
1026:
1024:
1021:
1019:
1016:
1015:
1012:
1009:
1006:
1002:
1000:
997:
995:
992:
990:
987:
985:
982:
980:
977:
976:
973:
970:
968:
965:
962:
958:
956:
953:
951:
948:
946:
943:
941:
938:
937:
934:
931:
929:
926:
924:
921:
918:
914:
912:
909:
907:
904:
902:
899:
898:
895:
892:
890:
887:
885:
882:
880:
877:
874:
870:
868:
865:
863:
860:
859:
856:
853:
851:
848:
846:
843:
841:
838:
836:
833:
830:
826:
824:
821:
820:
817:
814:
812:
809:
807:
804:
802:
799:
797:
794:
792:
789:
786:
782:
781:
740:
708:
695:
689:total ordering
655:
652:
640:
625:
566:
555:
545:
538:
520:
508:
496:
465:
446:
437:
386:
377:
370:
361:
350:
349:
338:
335:
330:
326:
322:
317:
313:
309:
306:
303:
300:
297:
294:
291:
286:
282:
278:
275:
272:
262:
257:
253:
249:
246:
243:
240:
237:
234:
229:
225:
221:
218:
215:
212:
209:
206:
203:
200:
197:
153:
146:
132:
131:
120:
117:
114:
111:
108:
105:
102:
99:
96:
93:
90:
87:
84:
81:
78:
75:
60:
57:
32:each possible
9:
6:
4:
3:
2:
2421:
2410:
2407:
2405:
2402:
2400:
2399:Combinatorics
2397:
2396:
2394:
2383:
2378:
2375:on 2004-11-16
2374:
2370:
2366:
2361:
2360:
2348:
2344:
2339:
2334:
2330:
2326:
2322:
2316:
2308:
2305:(in French),
2304:
2300:
2293:
2285:
2281:
2274:
2270:
2259:
2253:
2248:
2246:
2244:
2240:
2239:Wolfram Alpha
2230:
2227:
2223:
2218:
2214:
2212:
2206:
2201:
2191:
2189:
2185:
2164:
2161:
2151:
2146:
2137:
2128:
2120:
2116:
2110:
2105:
2102:
2099:
2095:
2091:
2085:
2079:
2071:
2069:
2048:
2043:
2039:
2036:
2033:
2030:
2027:
2021:
2015:
2007:
2003:
1994:
1975:
1969:
1965:
1959:
1951:
1933:
1927:
1924:
1918:
1912:
1909:
1906:
1903:
1897:
1891:
1880:
1871:
1865:
1854:
1848:
1845:
1839:
1833:
1822:
1813:
1807:
1791:
1777:
1767:
1764:
1761:
1742:
1724:
1716:
1710:
1706:
1700:
1692:
1689:
1686:
1683:
1680:
1676:
1672:
1666:
1658:
1654:
1638:
1632:
1628:
1622:
1614:
1611:
1608:
1605:
1602:
1598:
1594:
1588:
1580:
1576:
1567:
1565:
1561:
1557:
1549:
1527:
1521:
1518:
1515:
1512:
1506:
1503:
1500:
1494:
1479:
1473:
1470:
1467:
1451:
1448:
1442:
1439:
1436:
1430:
1415:
1409:
1406:
1403:
1392:
1390:
1371:
1350:
1346:
1342:
1338:
1333:
1331:
1327:
1320:
1313:
1309:
1305:
1301:
1284:
1282:
1278:
1274:
1269:
1264:
1260:
1255:
1251:
1247:
1228:
1225:
1222:
1219:
1216:
1213:
1210:
1207:
1204:
1194:-element set
1193:
1174:
1168:
1162:
1156:
1153:
1150:
1144:
1141:
1138:
1132:
1126:
1114:
1110:
1107:
1092:
1090:
1084:
1079:
1075:
1070:
1042:
1037:
1032:
1027:
1022:
1017:
1010:
998:
993:
988:
983:
978:
971:
966:
954:
949:
944:
939:
932:
927:
922:
910:
905:
900:
893:
888:
883:
878:
866:
861:
854:
849:
844:
839:
834:
822:
815:
810:
805:
800:
795:
790:
772:
771:
770:
767:
763:
759:
753:
746:
743:
738:
734:
730:
726:
721:
717:
711:
707:
703:
698:
694:
690:
683:
676:
670:
665:
661:
651:
649:
643:
639:
634:
628:
624:
620:
616:
612:
608:
604:
599:
597:
593:
589:
585:
580:
576:
569:
565:
558:
554:
548:
544:
537:
533:
529:
523:
518:
514:
506:
502:
494:
490:
485:
481:
477:
473:
468:
463:
459:
455:
449:
445:
440:
436:
430:
426:
421:
417:
412:
409:
405:
399:
395:
389:
385:
380:
376:
369:
364:
359:
355:
336:
328:
324:
320:
315:
311:
307:
304:
301:
298:
289:
284:
276:
270:
255:
247:
241:
238:
235:
232:
227:
219:
213:
207:
201:
195:
188:
187:
186:
184:
180:
174:
169:
165:
161:
156:
152:
145:
141:
137:
118:
115:
112:
109:
106:
103:
97:
94:
91:
85:
82:
79:
76:
73:
66:
65:
64:
56:
54:
49:
47:
43:
39:
35:
31:
27:
23:
22:combinatorics
19:
2404:Permutations
2381:
2373:the original
2368:
2357:Bibliography
2328:
2324:
2315:
2306:
2302:
2292:
2283:
2279:
2273:
2236:
2219:
2215:
2210:
2207:
2203:
2190:(unsigned).
2181:
2064:
2062:
1947:
1740:
1738:
1559:
1551:
1543:
1541:
1388:
1348:
1344:
1340:
1336:
1334:
1329:
1322:
1315:
1311:
1307:
1303:
1292:
1290:
1267:
1262:
1258:
1253:
1249:
1191:
1112:
1108:
1103:
1088:
1082:
1077:
1073:
1071:
1068:
765:
761:
757:
751:
747:
741:
736:
732:
728:
724:
719:
715:
709:
705:
701:
696:
692:
681:
674:
668:
663:
659:
657:
647:
641:
637:
632:
626:
622:
618:
614:
610:
609:) for fixed
606:
602:
600:
595:
587:
583:
582:at position
578:
574:
567:
563:
556:
552:
546:
542:
535:
527:
521:
516:
512:
504:
500:
492:
488:
483:
479:
475:
471:
466:
461:
457:
453:
447:
443:
438:
434:
428:
424:
419:
415:
413:
407:
403:
397:
393:
387:
383:
378:
374:
367:
362:
357:
353:
351:
178:
172:
167:
163:
159:
154:
150:
143:
139:
135:
133:
62:
50:
37:
25:
15:
2241:. See also
2220:Allegedly,
2182:(using the
1739:Indeed, as
1302:, there is
1277:independent
34:permutation
26:Lehmer code
18:mathematics
2393:Categories
2265:References
2211:a fortiori
1310:) at rank
2309:: 176–183
2286:: 179–193
2155:¯
2096:∏
2031:−
1910:−
1690:≤
1684:≤
1677:∑
1667:ω
1612:≤
1606:≤
1599:∑
1589:ω
1519:−
1507:ω
1489:⇔
1471:∈
1468:ω
1443:ω
1425:⇔
1407:∈
1404:ω
1226:−
1217:…
1169:×
1157:×
1154:⋯
1151:×
1142:−
1133:×
325:σ
312:σ
293:#
277:σ
248:σ
236:…
220:σ
202:σ
183:encodings
116:×
110:×
107:⋯
104:×
95:−
86:×
46:inversion
1347:", i.e.
59:The code
2347:2245639
1550:(resp.
1339:(resp.
1308:maximum
1306:(resp.
723:, and (
541:, ...,
478:) with
422:) with
373:, ...,
149:, ...,
48:table.
2345:
2141:
2135:
1752:
1698:
1620:
1360:
1330:i>k
511:+ … +
456:, and
406:+ 1 −
30:encode
24:, the
2343:JSTOR
1328:with
1299:1≤k≤n
718:>
619:value
442:>
427:<
266:where
179:every
1993:is
1948:The
1741:L(k)
1349:B(k)
1341:H(k)
1337:B(k)
1335:Let
1293:u=(u
432:and
321:<
302:>
2333:doi
2070:is
1649:and
1556:(ω)
1548:(ω)
1460:and
1314:if
1248:on
1085:− 1
754:− 1
745:.)
684:− 2
677:− 1
175:− 1
16:In
2395::
2367:,
2341:,
2327:,
2307:16
2301:,
2284:10
2282:,
2245:.
1283:.
577:−
499:+
396:−
2335::
2329:4
2165:!
2162:n
2152:n
2147:s
2138:=
2132:)
2129:s
2126:(
2121:k
2117:G
2111:n
2106:1
2103:=
2100:k
2092:=
2089:)
2086:s
2083:(
2080:G
2067:b
2065:N
2049:,
2044:k
2040:s
2037:+
2034:1
2028:k
2022:=
2019:)
2016:s
2013:(
2008:k
2004:G
1979:)
1976:k
1973:(
1970:B
1966:1
1960:1
1934:.
1928:k
1925:1
1919:=
1916:)
1913:1
1907:k
1904:=
1901:)
1898:k
1895:(
1892:L
1889:(
1885:P
1881:=
1878:)
1875:)
1872:k
1869:(
1866:H
1863:(
1859:P
1855:=
1852:)
1849:0
1846:=
1843:)
1840:k
1837:(
1834:L
1831:(
1827:P
1823:=
1820:)
1817:)
1814:k
1811:(
1808:B
1805:(
1801:P
1778:,
1775:]
1771:]
1768:k
1765:,
1762:1
1759:[
1755:[
1725:.
1720:)
1717:k
1714:(
1711:H
1707:1
1701:1
1693:n
1687:k
1681:1
1673:=
1670:)
1664:(
1659:b
1655:N
1642:)
1639:k
1636:(
1633:B
1629:1
1623:1
1615:n
1609:k
1603:1
1595:=
1592:)
1586:(
1581:b
1577:N
1560:ω
1554:h
1552:N
1546:b
1544:N
1528:.
1525:}
1522:1
1516:k
1513:=
1510:)
1504:,
1501:k
1498:(
1495:L
1492:{
1486:}
1483:)
1480:k
1477:(
1474:H
1465:{
1455:}
1452:0
1449:=
1446:)
1440:,
1437:k
1434:(
1431:L
1428:{
1422:}
1419:)
1416:k
1413:(
1410:B
1401:{
1389:k
1372:n
1366:S
1345:k
1325:i
1323:u
1318:k
1316:u
1312:k
1297:)
1295:k
1268:i
1265:)
1263:σ
1261:(
1259:L
1254:n
1250:S
1232:}
1229:1
1223:k
1220:,
1214:,
1211:1
1208:,
1205:0
1202:{
1192:k
1178:]
1175:1
1172:[
1166:]
1163:2
1160:[
1148:]
1145:1
1139:n
1136:[
1130:]
1127:n
1124:[
1113:n
1109:S
1089:n
1083:n
1078:x
1074:x
1049:0
1043:1
1038:1
1033:3
1028:0
1023:4
1018:1
1011:0
1005:1
999:1
994:3
989:0
984:4
979:1
972:0
967:2
961:1
955:3
950:0
945:4
940:1
933:0
928:2
923:1
917:3
911:0
906:4
901:1
894:1
889:3
884:2
879:4
873:0
867:4
862:1
855:1
850:3
845:2
840:5
835:0
829:4
823:1
816:2
811:4
806:3
801:6
796:0
791:5
785:1
766:x
762:x
758:x
752:n
742:i
739:)
737:σ
735:(
733:L
729:j
727:,
725:i
720:i
716:j
710:i
706:σ
702:i
697:i
693:σ
682:n
675:n
669:n
664:n
660:n
648:σ
642:j
638:σ
633:i
627:j
623:σ
615:i
611:j
607:j
605:,
603:i
596:n
588:σ
584:i
579:i
575:n
568:j
564:σ
557:i
553:σ
547:n
543:σ
539:1
536:σ
528:σ
522:n
519:)
517:σ
515:(
513:L
509:2
507:)
505:σ
503:(
501:L
497:1
495:)
493:σ
491:(
489:L
484:j
480:i
476:j
474:,
472:i
467:i
464:)
462:σ
460:(
458:L
454:σ
448:j
444:σ
439:i
435:σ
429:j
425:i
420:j
418:,
416:i
408:i
404:n
398:i
394:n
388:i
384:σ
379:n
375:σ
371:1
368:σ
363:i
360:)
358:σ
356:(
354:L
337:,
334:}
329:i
316:j
308::
305:i
299:j
296:{
290:=
285:i
281:)
274:(
271:L
261:)
256:n
252:)
245:(
242:L
239:,
233:,
228:1
224:)
217:(
214:L
211:(
208:=
205:)
199:(
196:L
173:n
168:n
164:n
160:n
155:n
151:σ
147:1
144:σ
140:σ
136:n
119:1
113:2
101:)
98:1
92:n
89:(
83:n
80:=
77:!
74:n
38:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
