10am-11:10am (US Central): Poster Session (Statistics in Permutations and Other Structures)

Moderator: Manda Riehl
(This is 8am US Pacific, 11am US Eastern, 3pm GMT, 4pm in the UK, 5pm CEST, 6pm in Israel, 11pm in China, 1am in Sydney, 3am in New Zealand)


Title: Pattern classes equinumerous to the class of ternary forests

Author: Alexander Burstein (Howard University)

Abstract: The enumeration sequence for the ternary forests (OEIS A098746) also enumerates (up to symmetries) 16 permutation pattern classes and 3 inversion sequence pattern classes. We present some results and conjectures on the distribution of several combinatorial statistics on those classes.

Poster: Burstein_poster

[Back to the top]

Title: Descents on quasi-Stirling permutations

Author: Sergi Elizalde (Dartmouth College)

Abstract: Stirling permutations were introduced by Gessel and Stanley in 1978, who enumerated them by the number of descents to give a combinatorial interpretation of certain polynomials related to Stirling numbers. A natural extension of these permutations are quasi-Stirling permutations, which can be viewed as labeled noncrossing matchings. They were recently introduced by Archer et al., motivated by the fact that Janson’s correspondence between Stirling permutations and labeled increasing plane trees extends to a bijection between quasi-Stirling permutations and the same set of trees without the increasing restriction.

In this talk we prove a conjecture of Archer et al. stating that there are (n+1)^(n-1) quasi-Stirling permutations of size n having n descents. More generally, we give the generating function for quasi-Stirling permutations by the number of descents, expressed as a compositional inverse of the generating function of Eulerian polynomials. We also find the analogue for quasi-Stirling permutations of the main result from Gessel and Stanley’s paper. We prove that the distribution of descents on these permutations is asymptotically normal, and that the roots of the corresponding quasi-Stirling polynomials are all real, in analogy to Bóna’s results for Stirling permutations.

Finally, we generalize our results to a one-parameter family of permutations that extends k-Stirling permutations, and we refine them by also keeping track of the number of ascents and the number of plateaus.

Poster: Elizalde_poster

[Back to the top]

Title: Enumeration of pattern-avoiding permutations with a prescribed number of inactive sites

Author: Juan B. Gil (Penn State Altoona)
Joint work with: David Kenepp (Penn State Altoona), Michael Weiner (Penn State Altoona)

Abstract: We study pattern-avoiding permutations (for patterns of size 3 or 4) with a prescribed number of inactive sites. For patterns of size 3, we give a (probably known) closed formula for the number of permutations having exactly m inactive sites. For patterns of size 4, we show that the number of pattern-avoiding permutations of size n with at most one inactive site is given by binom(2n-2,n-1), regardless of the pattern. On the opposite end, we give formulas for certain permutation classes with a maximal number of inactive sites.

Poster: Gil_poster

[Back to the top]

Title: Exploring bijections between permutations and inversion sequences

Author: Megan Martinez (Ithaca College)

Abstract: Inversion sequences are integer sequences where each entry is nonnegative and strictly less than its position number (for instance, 001324 is an inversion sequence while 001424 is not; the first 4 is too large). Such sequences of length n are well-known to be counted by n! and bijections between permutations and inversion sequences are plentiful; the most famous is undoubtedly the Lehmer code (and all its trivial variants) which encodes the position of inversions within a permutation.

Recently, the notion of patterns in inversion sequences have been introduced and has been systematically studied, yielding numerous enumerative results. Within many of these works, bijections between inversion sequences and permutations naturally arise. Some are specifically constructed to map between pattern-avoiding sets, but others are defined for unrestricted permutations and inversion sequences. In this latter case, many of these bijections can be restricted to create natural correspondences between multiple classes of pattern-avoiding permutations and inversion sequences.

While many of these bijections were used for the purpose of enumerating one class of inversion sequences, there are many “hidden results” that arise from application of the bijections. In this poster, we will discuss some of the most interesting bijections between permutations and inversion sequences that have been developed and what results can be plumbed from their depths.

Poster: Martinez_poster
Audio: Martinez_audio

[Back to the top]

Title: Bijective proofs of shuffle compatibility

Author: Bruce E Sagan (Michigan State University)
Joint work with: Duff Baker-Jarvis (Wake Forest University)

Abstract: PP2020_Sagan_abstract

Poster: Sagan_poster
Video: Sagan_video

[Back to the top]

Title: Counting permutations by peaks, descents, and cycle type

Author: Yan Zhuang (Davidson College)
Joint work with: Ira Gessel (Brandeis University)

Abstract: We present a general formula describing the joint distribution of two permutation statistics—the peak number and the descent number—over any set of permutations whose quasisymmetric generating function is a symmetric function. Our formula involves a certain kind of plethystic substitution on quasisymmetric generating functions. We apply this result to cyclic permutations, involutions, and derangements, and to give a generating function formula for counting permutations by peaks, descents, and cycle type. Along the way, we recover as special cases results previously derived by Gessel–Reutenauer, Fulman, Diaconis–Fulman–Holmes, and Athanasiadis.

Poster: Zhuang_poster

[Back to the top]

Back to the Workshop Program