Flattened partitions: pattern avoidance and behavior of permutation statistics

Abstract

The study of permutations, and specifically flattened partitions is an active area of current research. We provide a new combinatorial interpretation to the sequence A124324 in the On-line Encyclopedia of Integer Sequences (OEIS) database by means of a combinatorial bijection between flattened partitions over [n+1] and the partitions of [n]. We introduce the numbers fn,k which count the number of flattened partitions over [n] having k runs, and we give recurrence relations defining them, as well as their exponential generating function in differential form. We extend the results to flattened partitions where the first s integers belong to different runs. Combinatorial proofs are given. We further count the number of distinct flattened partitions over [n] avoiding a single pattern of length three, as well as a pair of such patterns. Several famous counting sequences, namely Catalan numbers, powers of two, Fibonacci numbers and Motzkin numbers arise. We also consider other combinatorial statistics, namely runs and inversions, and establish some bijections in situations where the statistics coincide.

We study a sorting procedure (run-sorting) on permutations, where runs are rearranged in lexicographic order. We describe a rather surprising bijection on permutations on length n, with the property that it sends the set of peak-values to the set of peak-values after run-sorting. We also prove that the expected number of descents in a permutation after run-sorting is equal to (n − 2)/3. We also provide a closed form of the exponential generating function introduced by Nabawanda, Rakotondrajao and Bamunoba in 2020, for the number of run-sorted permutations over [n], (RSP(n)) having k runs, which gives a new interpretation to the sequence A124324 on the OEIS database. We show that the descent generating polynomials, An(t) for RSP(n) are real rooted, and satisfy an interlacing property similar to that satisfied by the Eulerian polynomials.

Finally, we study run-sorted binary words and compute the expected number of descents after run-sorting a binary word of length n.