On the inner structure of a permutation: Bicolored Partitions and Eulerians Trees and Primitives

We present a bijective algorithm with which an arbitrary permutation decomposes canonically into elementary blocks which we call families, which are sets with a specified number of ascents and descents. We show that families, arranged in an arbitrary order in a sequence, are in bijection with permutations. The permutation decomposes canonically, by inserting parentheses, into a tree having as nodes a class of permutations which we call primitive. Primitive permutations can be assembled from very simple data. The data for the trees into which a permutation decomposes can be written in a form similar to the decimal classification of a library. We axiomatize that data. It has a structure very different from the permutation which it encodes, with shuffles and pair-ings instead of reorderings. These structures are similar to the fundamental processes in quantum field theory. Our main bijective structure algorithm gives explicit, additive multinomial formulae for the number of permutations with given sets of elements under and over the diagonal, or with given ascent and descent values. The multinomial expressions obtained this way give a new class of bicolored set statis-tics, between set partitions and set compositions, called shifted multinomials. These provide for the first time additive multinomial expressions for Eulerian numbers and de-rangements, as part of a sequence of new combinatorial objects. These multinomial expressions satisfy inductive relations involving only immediate neighbors, similar to the relations satisfied by the Eulerian numbers. 1 Preintroduction Much of this paper is based on the structure of a family. There are different equivalent ways to look at it. First, a family S is a set, together with a specified number k ascent values, or reds, and l descent values, or blues, with k, l ≥ 1, and k+1 = |S|. The information in the bicoloring of S can equivalently be given by making S into a sequence (r1, r2..., rk, bl, bl−1,..., b1), where b1 < b2 <... bl < r1 < r2 <... < rk, and {r1,..., rk} are the reds, the elements colored red in the set S, and {b1,..., bl} are the blues, the elements colored blue. We put both kinds of information together by viewing S as a colored sequence. 1 a