Stirling Permutations to Increasing Plane Trees and Back

Gavin Sayrs and Ariel Minakawa, “Stirling Permutations to Increasing Plane Trees and Back” 

Mentor: Pamela Harris, Mathematical Sciences, Letters & Science (College of) 

Poster #11 

A Stirling permutation is a permutation on the multiset {1,1, 2, 2, 3, 3, … ,n, n} such that any numbers appearing between repeated values of i must be greater than i.  Recall that a plane tree is a tree drawn on a plane with no edges crossing.  An increasing plane tree is a plane tree where each vertex is labeled from 1 to n, with labels increasing away from the root. Our main result establishes a bijection from Stirling permutations to its respective increasing plain tree.