2013/04/04 by Adrian Ocneanu, Ocneanu, Adrian · 2 citations
Mathematics · Computer Science · #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Bayesian Methods and Mixture Models
paper · pdf · doi:10.48550/arxiv.1304.1263
We present a bijective algorithm with which an arbitrary permutation\ndecomposes canonically into elementary blocks which we call families, which are\nsets with a specified number of ascents and descents. We show that families,\narranged in an arbitrary order in a sequence, are in bijection with\npermutations. The permutation decomposes canonically, by inserting parentheses,\ninto a tree having as nodes a class of permutations which we call primitive.\nPrimitive permutations can be assembled from very simple data. The data for the\ntrees into which a permutation decomposes can be written in a form similar to\nthe decimal classification of a library. We axiomatize that data. It has a\nstructure very different from the permutation which it encodes, with shuffles\nand pairings instead of reorderings. These structures are similar to the\nfundamental processes in quantum field theory. Our main bijective structure\nalgorithm gives explicit, additive multinomial formulae for the number of\npermutations with given sets of elements under and over the diagonal, or with\ngiven ascent and descent values. The multinomial expressions obtained this way\ngive a new class of bicolored set statistics, between set partitions and set\ncompositions, called shifted multinomials. These provide for the first time\nadditive multinomial expressions for Eulerian numbers and derangements, as part\nof a sequence of new combinatorial objects. These multinomial expressions\nsatisfy inductive relations involving only immediate neighbors, similar to the\nrelations satisfied by the Eulerian numbers.\n