GS Permutations and Riordan Codes

We define a GSr[n] permutation to be an arrangement of the multiset {1,2,...,n}r which is the end product of the following insertion algorithm: first insert the r-element string '1 1 .. 1' into the empty list ; then repeatedly insert the r-element strings '2 2 .. 2' , '3 3 .. 3', etc. into the list from the right, noting (as a code, which we call the Riordan code) how many single elements are transposed (or "bubbled") to the right of the latest insertion string.

Thus the Riordan codes are ordered n-tuples [a1,...,an] of non-negative integers such that aj < r (j-1) + 1. Riordan [BS4P] considered the case r=2 and counted those Riordan codes having exactly k+1 distinct a's in their codes. This gave a combinatorial interpretation to some numbers previously defined by Carlitz which have come to be known as the "Second-Order Eulerian Numbers" and nowadays denoted by <<n,k>>.

Subsequently, Gessel and Stanley [GS] showed that if we count GS2[n] permutations with exactly k+1 descents, the result is again <<n,k>>. The natural suspicion that [BS4P] and [GS] are dealing with the same equivalence relation proves unfounded, however, and there does not seem to be a natural bijection between the two classes of size <<n,k>>.

Time for an example: Let n=4 , k=1 , <<4,1>> = 22. The Riordan equivalence class of 22 permutations of {1 1 2 2 3 3 4 4} arising from a Riordan code of length 4 having exactly two distinct entries includes exactly two permutations which do not have exactly two descents:

Corresponding to the Riordan code "0 1 0 1" we have {1 2 2 1 3 4 4 3}, which has three descents (the final 'drop-off' is always counted); and the code "0 2 0 2" produces {2 2 1 1 4 4 3 3}, also with three.

Of course there must be two permutations HAVING exactly 2 descents whose Riordan codes do not have exactly two distinct entries: {1 2 2 4 4 1 3 3} which is decoded as "0 1 0 3", and {2 2 4 4 1 1 3 3} from "0 2 0 4". The other 20 permutations in each class are identical. For the classes of size <<4,3>> = 24, the intersection size is 23.

Given a GS2[n] permutation it is certainly faster to determine its descent class than to Riordan-decode it, but we note that both statistics are essential properties of the permutation. It is of historical interest to note that a very similar phenomenon appeared to Maj. P. MacMahon in 1916 [MacM]: while studying two other statistics on permutations of multisets he again found same-size equivalence classes without finding natural bijections between them.

His first characteristic was the "greater index". To calculate the greater index we sum the place-numbers of each first element of a descent (but ignoring the final drop-off). Thus the greater index of {1 2 2 1 3 4 4 3} is 3+7=10, while that of {2 2 1 1 4 4 3 3} is 2+6=8. MacMahon's second statistic is the inversion number which increments for each entry by the number of smaller entries to its right. The last two examples evaluate to inversion numbers 4 and 8, respectively. Nevertheless, MacMahon shows that a given number determines the same size class of permutations, whether the number is interpreted as major index or inversion number. Again one statistic is 'single-pass' (descents, greater indices) and the other 'multi-pass' (Riordan code, inversions).

The proofs for these facts are not difficult: MacMahon used generating functions directly, while [GS] and [BS4P] verified recurrence relations.

[GS] Gessel, I., Stanley, R., Stirling Polynomials, J. Comb. Theory, Ser. A, 24, 24-33 (1978)

[MacM] MacMahon, P., Two Applications of General Theorems in Combinatory Analysis, Proc. London Math. Soc.(2), 15, 314-321 (1916)

[BS4P] Riordan, J., The Blossoming of Schroeder's Fourth Problem, Acta Math.,137, 1-16 (1976)

Len M. Smiley
Last modified: Wed Nov 21 00:28:34 AKST 2001