Henning Ulfarsson: Counting permutations by inversions

ABSTRACT:

This is joint work with Anders Claesson, Christian Bean, Atli Fannar Franklin and Jay Pantone.

A permutation is sum-indecomposable if it can not be written as a direct sum of two non-empty permutations. Every permutation can be written as a direct sum of indecomposable permutations, called its components. The following result appears in Claesson, Jelinek, and Steingrimsson (2012).

For a permutation of length n with c components and k inversions, we have that c + k is at least as large as n.

Let IS_k be the set of indecomposable permutations with k inversions. The result above implies that IS_k is finite. In this talk, we will study subsets of IS_k that avoid classical patterns. We use IS_k(B) to denote the subset of permutations in IS_k that avoid all of the patterns in B. Some of our results are summarized below.

- The set IS_k(12) is enumerated by the characteristic function of triangular numbers.

- The set IS_k(132) is enumerated by the number of partitions of k.

- The set IS_k(231) is enumerated by the number of fountains on k coins.

- The set IS_k(321) is enumerated by the number of parallelogram polyominoes with k cells.

We will also mention sets defined by the avoidance of longer patterns, as well as how these counting sequences can be used to bound the usual counting sequences of permutation classes by length.

One can also consider the problem of counting sets of permutations by other statistics, besides inversions, as well as using a different restriction than indecomposability.