Create Your Own Permutation Statistics
Emeric Deutsch, Warren P. Johnson · Mathematics Magazine · 2004
A permutation of length n is, for us, a list of the numbers {1, 2, . . ., n} in some order, so that (for example) 27163854 is a permutation of length 8.* An inversion in a permutation is any pair of numbers, not necessarily consecutive, that are of in the sense that the larger number occurs before the smaller one; thus 7 and 5 are an inversion in 27163854, and you can check that there are eleven others. We say that the inversion number of 27163854 is 12. The inversion number occurs at least implicitly in the definition of a determinant as a sum over permutations inversions by which a permutation differs from increasing order are equivalent to row exchanges needed to change a permutation matrix into the identityand the concept dates back to Cramer's pioneering work on determinants in 1750 [4]. (The term inversions seems to date from expository work on determinants by Gergonne in 1813 [9] and Garnier [8] the following year; Cramer called them derangements. See Muir [15] for more details.) It is probably the second best known example of what is called a permutation statistic, which is just a function (typically nonnegative and integer-valued) defined on permutations. The best known example is the number of cycles, and Thanatipanonda's note in this issue discusses what may be the third best known example. There are some wonderful results about inversions [10, 17, 18], but it is not our purpose to discuss them here. Rather we want to point out an easy way to construct another class of permutation statistics: Given a property P that a permutation Z may or may not have, we can record the length of the longest initial segment of Z that has property P. We will prove a simple result about this type of statistic, and look at some nice examples. We will try to maintain a distinction between permutations and sequences. By a sequence of length n we shall mean a list of n distinct positive integers, which may or may not be {1, 2, . . ., n}, in some order. To each sequence of length n we associate a permutation of length n in the natural way, by relabeling the smallest number in the sequence as 1, the second smallest number as 2, and so on, relabeling the largest number as n. We call this permutation the reduction of the sequence; for example, the reduction of 428396 is 315264. We also define the truncation of a sequence a to be a with its last element deleted; for example, the truncation of 2371 is 237. We will focus on properties P satisfying two conditions: